Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Instrumentation/ThreadSanitizer.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- ThreadSanitizer.cpp - race detector -------------------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file is a part of ThreadSanitizer, a race detector.
10
//
11
// The tool is under development, for the details about previous versions see
12
// http://code.google.com/p/data-race-test
13
//
14
// The instrumentation phase is quite simple:
15
//   - Insert calls to run-time library before every memory access.
16
//      - Optimizations may apply to avoid instrumenting some of the accesses.
17
//   - Insert calls at function entry/exit.
18
// The rest is handled by the run-time library.
19
//===----------------------------------------------------------------------===//
20
21
#include "llvm/Transforms/Instrumentation/ThreadSanitizer.h"
22
#include "llvm/ADT/SmallPtrSet.h"
23
#include "llvm/ADT/SmallString.h"
24
#include "llvm/ADT/SmallVector.h"
25
#include "llvm/ADT/Statistic.h"
26
#include "llvm/ADT/StringExtras.h"
27
#include "llvm/Analysis/CaptureTracking.h"
28
#include "llvm/Analysis/TargetLibraryInfo.h"
29
#include "llvm/Transforms/Utils/Local.h"
30
#include "llvm/Analysis/ValueTracking.h"
31
#include "llvm/IR/DataLayout.h"
32
#include "llvm/IR/Function.h"
33
#include "llvm/IR/IRBuilder.h"
34
#include "llvm/IR/IntrinsicInst.h"
35
#include "llvm/IR/Intrinsics.h"
36
#include "llvm/IR/LLVMContext.h"
37
#include "llvm/IR/Metadata.h"
38
#include "llvm/IR/Module.h"
39
#include "llvm/IR/Type.h"
40
#include "llvm/ProfileData/InstrProf.h"
41
#include "llvm/Support/CommandLine.h"
42
#include "llvm/Support/Debug.h"
43
#include "llvm/Support/MathExtras.h"
44
#include "llvm/Support/raw_ostream.h"
45
#include "llvm/Transforms/Instrumentation.h"
46
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
47
#include "llvm/Transforms/Utils/EscapeEnumerator.h"
48
#include "llvm/Transforms/Utils/ModuleUtils.h"
49
50
using namespace llvm;
51
52
#define DEBUG_TYPE "tsan"
53
54
static cl::opt<bool>  ClInstrumentMemoryAccesses(
55
    "tsan-instrument-memory-accesses", cl::init(true),
56
    cl::desc("Instrument memory accesses"), cl::Hidden);
57
static cl::opt<bool>  ClInstrumentFuncEntryExit(
58
    "tsan-instrument-func-entry-exit", cl::init(true),
59
    cl::desc("Instrument function entry and exit"), cl::Hidden);
60
static cl::opt<bool>  ClHandleCxxExceptions(
61
    "tsan-handle-cxx-exceptions", cl::init(true),
62
    cl::desc("Handle C++ exceptions (insert cleanup blocks for unwinding)"),
63
    cl::Hidden);
64
static cl::opt<bool>  ClInstrumentAtomics(
65
    "tsan-instrument-atomics", cl::init(true),
66
    cl::desc("Instrument atomics"), cl::Hidden);
67
static cl::opt<bool>  ClInstrumentMemIntrinsics(
68
    "tsan-instrument-memintrinsics", cl::init(true),
69
    cl::desc("Instrument memintrinsics (memset/memcpy/memmove)"), cl::Hidden);
70
71
STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
72
STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
73
STATISTIC(NumOmittedReadsBeforeWrite,
74
          "Number of reads ignored due to following writes");
75
STATISTIC(NumAccessesWithBadSize, "Number of accesses with bad size");
76
STATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes");
77
STATISTIC(NumInstrumentedVtableReads, "Number of vtable ptr reads");
78
STATISTIC(NumOmittedReadsFromConstantGlobals,
79
          "Number of reads from constant globals");
80
STATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads");
81
STATISTIC(NumOmittedNonCaptured, "Number of accesses ignored due to capturing");
82
83
static const char *const kTsanModuleCtorName = "tsan.module_ctor";
84
static const char *const kTsanInitName = "__tsan_init";
85
86
namespace {
87
88
/// ThreadSanitizer: instrument the code in module to find races.
89
///
90
/// Instantiating ThreadSanitizer inserts the tsan runtime library API function
91
/// declarations into the module if they don't exist already. Instantiating
92
/// ensures the __tsan_init function is in the list of global constructors for
93
/// the module.
94
struct ThreadSanitizer {
95
  ThreadSanitizer(Module &M);
96
  bool sanitizeFunction(Function &F, const TargetLibraryInfo &TLI);
97
98
private:
99
  void initializeCallbacks(Module &M);
100
  bool instrumentLoadOrStore(Instruction *I, const DataLayout &DL);
101
  bool instrumentAtomic(Instruction *I, const DataLayout &DL);
102
  bool instrumentMemIntrinsic(Instruction *I);
103
  void chooseInstructionsToInstrument(SmallVectorImpl<Instruction *> &Local,
104
                                      SmallVectorImpl<Instruction *> &All,
105
                                      const DataLayout &DL);
106
  bool addrPointsToConstantData(Value *Addr);
107
  int getMemoryAccessFuncIndex(Value *Addr, const DataLayout &DL);
108
  void InsertRuntimeIgnores(Function &F);
109
110
  Type *IntptrTy;
111
  IntegerType *OrdTy;
112
  // Callbacks to run-time library are computed in doInitialization.
113
  FunctionCallee TsanFuncEntry;
114
  FunctionCallee TsanFuncExit;
115
  FunctionCallee TsanIgnoreBegin;
116
  FunctionCallee TsanIgnoreEnd;
117
  // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
118
  static const size_t kNumberOfAccessSizes = 5;
119
  FunctionCallee TsanRead[kNumberOfAccessSizes];
120
  FunctionCallee TsanWrite[kNumberOfAccessSizes];
121
  FunctionCallee TsanUnalignedRead[kNumberOfAccessSizes];
122
  FunctionCallee TsanUnalignedWrite[kNumberOfAccessSizes];
123
  FunctionCallee TsanAtomicLoad[kNumberOfAccessSizes];
124
  FunctionCallee TsanAtomicStore[kNumberOfAccessSizes];
125
  FunctionCallee TsanAtomicRMW[AtomicRMWInst::LAST_BINOP + 1]
126
                              [kNumberOfAccessSizes];
127
  FunctionCallee TsanAtomicCAS[kNumberOfAccessSizes];
128
  FunctionCallee TsanAtomicThreadFence;
129
  FunctionCallee TsanAtomicSignalFence;
130
  FunctionCallee TsanVptrUpdate;
131
  FunctionCallee TsanVptrLoad;
132
  FunctionCallee MemmoveFn, MemcpyFn, MemsetFn;
133
  Function *TsanCtorFunction;
134
};
135
136
struct ThreadSanitizerLegacyPass : FunctionPass {
137
31
  ThreadSanitizerLegacyPass() : FunctionPass(ID) {}
138
  StringRef getPassName() const override;
139
  void getAnalysisUsage(AnalysisUsage &AU) const override;
140
  bool runOnFunction(Function &F) override;
141
  bool doInitialization(Module &M) override;
142
  static char ID; // Pass identification, replacement for typeid.
143
private:
144
  Optional<ThreadSanitizer> TSan;
145
};
146
}  // namespace
147
148
PreservedAnalyses ThreadSanitizerPass::run(Function &F,
149
17
                                           FunctionAnalysisManager &FAM) {
150
17
  ThreadSanitizer TSan(*F.getParent());
151
17
  if (TSan.sanitizeFunction(F, FAM.getResult<TargetLibraryAnalysis>(F)))
152
10
    return PreservedAnalyses::none();
153
7
  return PreservedAnalyses::all();
154
7
}
155
156
char ThreadSanitizerLegacyPass::ID = 0;
157
11.0k
INITIALIZE_PASS_BEGIN(ThreadSanitizerLegacyPass, "tsan",
158
11.0k
                      "ThreadSanitizer: detects data races.", false, false)
159
11.0k
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
160
11.0k
INITIALIZE_PASS_END(ThreadSanitizerLegacyPass, "tsan",
161
                    "ThreadSanitizer: detects data races.", false, false)
162
163
391
StringRef ThreadSanitizerLegacyPass::getPassName() const {
164
391
  return "ThreadSanitizerLegacyPass";
165
391
}
166
167
31
void ThreadSanitizerLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
168
31
  AU.addRequired<TargetLibraryInfoWrapperPass>();
169
31
}
170
171
31
bool ThreadSanitizerLegacyPass::doInitialization(Module &M) {
172
31
  TSan.emplace(M);
173
31
  return true;
174
31
}
175
176
391
bool ThreadSanitizerLegacyPass::runOnFunction(Function &F) {
177
391
  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
178
391
  TSan->sanitizeFunction(F, TLI);
179
391
  return true;
180
391
}
181
182
14
FunctionPass *llvm::createThreadSanitizerLegacyPassPass() {
183
14
  return new ThreadSanitizerLegacyPass();
184
14
}
185
186
371
void ThreadSanitizer::initializeCallbacks(Module &M) {
187
371
  IRBuilder<> IRB(M.getContext());
188
371
  AttributeList Attr;
189
371
  Attr = Attr.addAttribute(M.getContext(), AttributeList::FunctionIndex,
190
371
                           Attribute::NoUnwind);
191
371
  // Initialize the callbacks.
192
371
  TsanFuncEntry = M.getOrInsertFunction("__tsan_func_entry", Attr,
193
371
                                        IRB.getVoidTy(), IRB.getInt8PtrTy());
194
371
  TsanFuncExit =
195
371
      M.getOrInsertFunction("__tsan_func_exit", Attr, IRB.getVoidTy());
196
371
  TsanIgnoreBegin = M.getOrInsertFunction("__tsan_ignore_thread_begin", Attr,
197
371
                                          IRB.getVoidTy());
198
371
  TsanIgnoreEnd =
199
371
      M.getOrInsertFunction("__tsan_ignore_thread_end", Attr, IRB.getVoidTy());
200
371
  OrdTy = IRB.getInt32Ty();
201
2.22k
  for (size_t i = 0; i < kNumberOfAccessSizes; 
++i1.85k
) {
202
1.85k
    const unsigned ByteSize = 1U << i;
203
1.85k
    const unsigned BitSize = ByteSize * 8;
204
1.85k
    std::string ByteSizeStr = utostr(ByteSize);
205
1.85k
    std::string BitSizeStr = utostr(BitSize);
206
1.85k
    SmallString<32> ReadName("__tsan_read" + ByteSizeStr);
207
1.85k
    TsanRead[i] = M.getOrInsertFunction(ReadName, Attr, IRB.getVoidTy(),
208
1.85k
                                        IRB.getInt8PtrTy());
209
1.85k
210
1.85k
    SmallString<32> WriteName("__tsan_write" + ByteSizeStr);
211
1.85k
    TsanWrite[i] = M.getOrInsertFunction(WriteName, Attr, IRB.getVoidTy(),
212
1.85k
                                         IRB.getInt8PtrTy());
213
1.85k
214
1.85k
    SmallString<64> UnalignedReadName("__tsan_unaligned_read" + ByteSizeStr);
215
1.85k
    TsanUnalignedRead[i] = M.getOrInsertFunction(
216
1.85k
        UnalignedReadName, Attr, IRB.getVoidTy(), IRB.getInt8PtrTy());
217
1.85k
218
1.85k
    SmallString<64> UnalignedWriteName("__tsan_unaligned_write" + ByteSizeStr);
219
1.85k
    TsanUnalignedWrite[i] = M.getOrInsertFunction(
220
1.85k
        UnalignedWriteName, Attr, IRB.getVoidTy(), IRB.getInt8PtrTy());
221
1.85k
222
1.85k
    Type *Ty = Type::getIntNTy(M.getContext(), BitSize);
223
1.85k
    Type *PtrTy = Ty->getPointerTo();
224
1.85k
    SmallString<32> AtomicLoadName("__tsan_atomic" + BitSizeStr + "_load");
225
1.85k
    TsanAtomicLoad[i] =
226
1.85k
        M.getOrInsertFunction(AtomicLoadName, Attr, Ty, PtrTy, OrdTy);
227
1.85k
228
1.85k
    SmallString<32> AtomicStoreName("__tsan_atomic" + BitSizeStr + "_store");
229
1.85k
    TsanAtomicStore[i] = M.getOrInsertFunction(
230
1.85k
        AtomicStoreName, Attr, IRB.getVoidTy(), PtrTy, Ty, OrdTy);
231
1.85k
232
1.85k
    for (int op = AtomicRMWInst::FIRST_BINOP;
233
25.9k
        op <= AtomicRMWInst::LAST_BINOP; 
++op24.1k
) {
234
24.1k
      TsanAtomicRMW[op][i] = nullptr;
235
24.1k
      const char *NamePart = nullptr;
236
24.1k
      if (op == AtomicRMWInst::Xchg)
237
1.85k
        NamePart = "_exchange";
238
22.2k
      else if (op == AtomicRMWInst::Add)
239
1.85k
        NamePart = "_fetch_add";
240
20.4k
      else if (op == AtomicRMWInst::Sub)
241
1.85k
        NamePart = "_fetch_sub";
242
18.5k
      else if (op == AtomicRMWInst::And)
243
1.85k
        NamePart = "_fetch_and";
244
16.6k
      else if (op == AtomicRMWInst::Or)
245
1.85k
        NamePart = "_fetch_or";
246
14.8k
      else if (op == AtomicRMWInst::Xor)
247
1.85k
        NamePart = "_fetch_xor";
248
12.9k
      else if (op == AtomicRMWInst::Nand)
249
1.85k
        NamePart = "_fetch_nand";
250
11.1k
      else
251
11.1k
        continue;
252
12.9k
      SmallString<32> RMWName("__tsan_atomic" + itostr(BitSize) + NamePart);
253
12.9k
      TsanAtomicRMW[op][i] =
254
12.9k
          M.getOrInsertFunction(RMWName, Attr, Ty, PtrTy, Ty, OrdTy);
255
12.9k
    }
256
1.85k
257
1.85k
    SmallString<32> AtomicCASName("__tsan_atomic" + BitSizeStr +
258
1.85k
                                  "_compare_exchange_val");
259
1.85k
    TsanAtomicCAS[i] = M.getOrInsertFunction(AtomicCASName, Attr, Ty, PtrTy, Ty,
260
1.85k
                                             Ty, OrdTy, OrdTy);
261
1.85k
  }
262
371
  TsanVptrUpdate =
263
371
      M.getOrInsertFunction("__tsan_vptr_update", Attr, IRB.getVoidTy(),
264
371
                            IRB.getInt8PtrTy(), IRB.getInt8PtrTy());
265
371
  TsanVptrLoad = M.getOrInsertFunction("__tsan_vptr_read", Attr,
266
371
                                       IRB.getVoidTy(), IRB.getInt8PtrTy());
267
371
  TsanAtomicThreadFence = M.getOrInsertFunction("__tsan_atomic_thread_fence",
268
371
                                                Attr, IRB.getVoidTy(), OrdTy);
269
371
  TsanAtomicSignalFence = M.getOrInsertFunction("__tsan_atomic_signal_fence",
270
371
                                                Attr, IRB.getVoidTy(), OrdTy);
271
371
272
371
  MemmoveFn =
273
371
      M.getOrInsertFunction("memmove", Attr, IRB.getInt8PtrTy(),
274
371
                            IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IntptrTy);
275
371
  MemcpyFn =
276
371
      M.getOrInsertFunction("memcpy", Attr, IRB.getInt8PtrTy(),
277
371
                            IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IntptrTy);
278
371
  MemsetFn =
279
371
      M.getOrInsertFunction("memset", Attr, IRB.getInt8PtrTy(),
280
371
                            IRB.getInt8PtrTy(), IRB.getInt32Ty(), IntptrTy);
281
371
}
282
283
48
ThreadSanitizer::ThreadSanitizer(Module &M) {
284
48
  const DataLayout &DL = M.getDataLayout();
285
48
  IntptrTy = DL.getIntPtrType(M.getContext());
286
48
  std::tie(TsanCtorFunction, std::ignore) =
287
48
      getOrCreateSanitizerCtorAndInitFunctions(
288
48
          M, kTsanModuleCtorName, kTsanInitName, /*InitArgTypes=*/{},
289
48
          /*InitArgs=*/{},
290
48
          // This callback is invoked when the functions are created the first
291
48
          // time. Hook them into the global ctors list in that case:
292
48
          [&](Function *Ctor, FunctionCallee) {
293
37
            appendToGlobalCtors(M, Ctor, 0);
294
37
          });
295
48
}
296
297
86
static bool isVtableAccess(Instruction *I) {
298
86
  if (MDNode *Tag = I->getMetadata(LLVMContext::MD_tbaa))
299
28
    return Tag->isTBAAVtableAccess();
300
58
  return false;
301
58
}
302
303
// Do not instrument known races/"benign races" that come from compiler
304
// instrumentatin. The user has no way of suppressing them.
305
210
static bool shouldInstrumentReadWriteFromAddress(const Module *M, Value *Addr) {
306
210
  // Peel off GEPs and BitCasts.
307
210
  Addr = Addr->stripInBoundsOffsets();
308
210
309
210
  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
310
32
    if (GV->hasSection()) {
311
8
      StringRef SectionName = GV->getSection();
312
8
      // Check if the global is in the PGO counters section.
313
8
      auto OF = Triple(M->getTargetTriple()).getObjectFormat();
314
8
      if (SectionName.endswith(
315
8
              getInstrProfSectionName(IPSK_cnts, OF, /*AddSegmentInfo=*/false)))
316
6
        return false;
317
26
    }
318
26
319
26
    // Check if the global is private gcov data.
320
26
    if (GV->getName().startswith("__llvm_gcov") ||
321
26
        
GV->getName().startswith("__llvm_gcda")20
)
322
8
      return false;
323
196
  }
324
196
325
196
  // Do not instrument acesses from different address spaces; we cannot deal
326
196
  // with them.
327
196
  if (Addr) {
328
196
    Type *PtrTy = cast<PointerType>(Addr->getType()->getScalarType());
329
196
    if (PtrTy->getPointerAddressSpace() != 0)
330
1
      return false;
331
195
  }
332
195
333
195
  return true;
334
195
}
335
336
101
bool ThreadSanitizer::addrPointsToConstantData(Value *Addr) {
337
101
  // If this is a GEP, just analyze its pointer operand.
338
101
  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr))
339
6
    Addr = GEP->getPointerOperand();
340
101
341
101
  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
342
6
    if (GV->isConstant()) {
343
2
      // Reads from constant globals can not race with any writes.
344
2
      NumOmittedReadsFromConstantGlobals++;
345
2
      return true;
346
2
    }
347
95
  } else if (LoadInst *L = dyn_cast<LoadInst>(Addr)) {
348
17
    if (isVtableAccess(L)) {
349
5
      // Reads from a vtable pointer can not race with any writes.
350
5
      NumOmittedReadsFromVtable++;
351
5
      return true;
352
5
    }
353
94
  }
354
94
  return false;
355
94
}
356
357
// Instrumenting some of the accesses may be proven redundant.
358
// Currently handled:
359
//  - read-before-write (within same BB, no calls between)
360
//  - not captured variables
361
//
362
// We do not handle some of the patterns that should not survive
363
// after the classic compiler optimizations.
364
// E.g. two reads from the same temp should be eliminated by CSE,
365
// two writes should be eliminated by DSE, etc.
366
//
367
// 'Local' is a vector of insns within the same BB (no calls between).
368
// 'All' is a vector of insns that will be instrumented.
369
void ThreadSanitizer::chooseInstructionsToInstrument(
370
    SmallVectorImpl<Instruction *> &Local, SmallVectorImpl<Instruction *> &All,
371
448
    const DataLayout &DL) {
372
448
  SmallPtrSet<Value*, 8> WriteTargets;
373
448
  // Iterate from the end.
374
448
  for (Instruction *I : reverse(Local)) {
375
210
    if (StoreInst *Store = dyn_cast<StoreInst>(I)) {
376
96
      Value *Addr = Store->getPointerOperand();
377
96
      if (!shouldInstrumentReadWriteFromAddress(I->getModule(), Addr))
378
7
        continue;
379
89
      WriteTargets.insert(Addr);
380
114
    } else {
381
114
      LoadInst *Load = cast<LoadInst>(I);
382
114
      Value *Addr = Load->getPointerOperand();
383
114
      if (!shouldInstrumentReadWriteFromAddress(I->getModule(), Addr))
384
8
        continue;
385
106
      if (WriteTargets.count(Addr)) {
386
5
        // We will write to this temp, so no reason to analyze the read.
387
5
        NumOmittedReadsBeforeWrite++;
388
5
        continue;
389
5
      }
390
101
      if (addrPointsToConstantData(Addr)) {
391
7
        // Addr points to some constant data -- it can not race with any writes.
392
7
        continue;
393
7
      }
394
183
    }
395
183
    Value *Addr = isa<StoreInst>(*I)
396
183
        ? 
cast<StoreInst>(I)->getPointerOperand()89
397
183
        : 
cast<LoadInst>(I)->getPointerOperand()94
;
398
183
    if (isa<AllocaInst>(GetUnderlyingObject(Addr, DL)) &&
399
183
        
!PointerMayBeCaptured(Addr, true, true)98
) {
400
92
      // The variable is addressable but not captured, so it cannot be
401
92
      // referenced from a different thread and participate in a data race
402
92
      // (see llvm/Analysis/CaptureTracking.h for details).
403
92
      NumOmittedNonCaptured++;
404
92
      continue;
405
92
    }
406
91
    All.push_back(I);
407
91
  }
408
448
  Local.clear();
409
448
}
410
411
1.08k
static bool isAtomic(Instruction *I) {
412
1.08k
  // TODO: Ask TTI whether synchronization scope is between threads.
413
1.08k
  if (LoadInst *LI = dyn_cast<LoadInst>(I))
414
138
    return LI->isAtomic() && 
LI->getSyncScopeID() != SyncScope::SingleThread24
;
415
945
  if (StoreInst *SI = dyn_cast<StoreInst>(I))
416
120
    return SI->isAtomic() && 
SI->getSyncScopeID() != SyncScope::SingleThread24
;
417
825
  if (isa<AtomicRMWInst>(I))
418
176
    return true;
419
649
  if (isa<AtomicCmpXchgInst>(I))
420
26
    return true;
421
623
  if (isa<FenceInst>(I))
422
8
    return true;
423
615
  return false;
424
615
}
425
426
4
void ThreadSanitizer::InsertRuntimeIgnores(Function &F) {
427
4
  IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
428
4
  IRB.CreateCall(TsanIgnoreBegin);
429
4
  EscapeEnumerator EE(F, "tsan_ignore_cleanup", ClHandleCxxExceptions);
430
8
  while (IRBuilder<> *AtExit = EE.Next()) {
431
4
    AtExit->CreateCall(TsanIgnoreEnd);
432
4
  }
433
4
}
434
435
bool ThreadSanitizer::sanitizeFunction(Function &F,
436
408
                                       const TargetLibraryInfo &TLI) {
437
408
  // This is required to prevent instrumenting call to __tsan_init from within
438
408
  // the module constructor.
439
408
  if (&F == TsanCtorFunction)
440
37
    return false;
441
371
  initializeCallbacks(*F.getParent());
442
371
  SmallVector<Instruction*, 8> AllLoadsAndStores;
443
371
  SmallVector<Instruction*, 8> LocalLoadsAndStores;
444
371
  SmallVector<Instruction*, 8> AtomicAccesses;
445
371
  SmallVector<Instruction*, 8> MemIntrinCalls;
446
371
  bool Res = false;
447
371
  bool HasCalls = false;
448
371
  bool SanitizeFunction = F.hasFnAttribute(Attribute::SanitizeThread);
449
371
  const DataLayout &DL = F.getParent()->getDataLayout();
450
371
451
371
  // Traverse all instructions, collect loads/stores/returns, check for calls.
452
383
  for (auto &BB : F) {
453
1.08k
    for (auto &Inst : BB) {
454
1.08k
      if (isAtomic(&Inst))
455
258
        AtomicAccesses.push_back(&Inst);
456
825
      else if (isa<LoadInst>(Inst) || 
isa<StoreInst>(Inst)711
)
457
210
        LocalLoadsAndStores.push_back(&Inst);
458
615
      else if (isa<CallInst>(Inst) || 
isa<InvokeInst>(Inst)550
) {
459
65
        if (CallInst *CI = dyn_cast<CallInst>(&Inst))
460
65
          maybeMarkSanitizerLibraryCallNoBuiltin(CI, &TLI);
461
65
        if (isa<MemIntrinsic>(Inst))
462
6
          MemIntrinCalls.push_back(&Inst);
463
65
        HasCalls = true;
464
65
        chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores,
465
65
                                       DL);
466
65
      }
467
1.08k
    }
468
383
    chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores, DL);
469
383
  }
470
371
471
371
  // We have collected all loads and stores.
472
371
  // FIXME: many of these accesses do not need to be checked for races
473
371
  // (e.g. variables that do not escape, etc).
474
371
475
371
  // Instrument memory accesses only if we want to report bugs in the function.
476
371
  if (ClInstrumentMemoryAccesses && SanitizeFunction)
477
90
    for (auto Inst : AllLoadsAndStores) {
478
73
      Res |= instrumentLoadOrStore(Inst, DL);
479
73
    }
480
371
481
371
  // Instrument atomic memory accesses in any case (they can be used to
482
371
  // implement synchronization).
483
371
  if (ClInstrumentAtomics)
484
371
    for (auto Inst : AtomicAccesses) {
485
258
      Res |= instrumentAtomic(Inst, DL);
486
258
    }
487
371
488
371
  if (ClInstrumentMemIntrinsics && SanitizeFunction)
489
90
    for (auto Inst : MemIntrinCalls) {
490
6
      Res |= instrumentMemIntrinsic(Inst);
491
6
    }
492
371
493
371
  if (F.hasFnAttribute("sanitize_thread_no_checking_at_run_time")) {
494
6
    assert(!F.hasFnAttribute(Attribute::SanitizeThread));
495
6
    if (HasCalls)
496
4
      InsertRuntimeIgnores(F);
497
6
  }
498
371
499
371
  // Instrument function entry/exit points if there were instrumented accesses.
500
371
  if ((Res || 
HasCalls60
) &&
ClInstrumentFuncEntryExit346
) {
501
346
    IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
502
346
    Value *ReturnAddress = IRB.CreateCall(
503
346
        Intrinsic::getDeclaration(F.getParent(), Intrinsic::returnaddress),
504
346
        IRB.getInt32(0));
505
346
    IRB.CreateCall(TsanFuncEntry, ReturnAddress);
506
346
507
346
    EscapeEnumerator EE(F, "tsan_cleanup", ClHandleCxxExceptions);
508
696
    while (IRBuilder<> *AtExit = EE.Next()) {
509
350
      AtExit->CreateCall(TsanFuncExit, {});
510
350
    }
511
346
    Res = true;
512
346
  }
513
371
  return Res;
514
371
}
515
516
bool ThreadSanitizer::instrumentLoadOrStore(Instruction *I,
517
73
                                            const DataLayout &DL) {
518
73
  IRBuilder<> IRB(I);
519
73
  bool IsWrite = isa<StoreInst>(*I);
520
73
  Value *Addr = IsWrite
521
73
      ? 
cast<StoreInst>(I)->getPointerOperand()31
522
73
      : 
cast<LoadInst>(I)->getPointerOperand()42
;
523
73
524
73
  // swifterror memory addresses are mem2reg promoted by instruction selection.
525
73
  // As such they cannot have regular uses like an instrumentation function and
526
73
  // it makes no sense to track them as memory.
527
73
  if (Addr->isSwiftError())
528
4
    return false;
529
69
530
69
  int Idx = getMemoryAccessFuncIndex(Addr, DL);
531
69
  if (Idx < 0)
532
0
    return false;
533
69
  if (IsWrite && 
isVtableAccess(I)27
) {
534
7
    LLVM_DEBUG(dbgs() << "  VPTR : " << *I << "\n");
535
7
    Value *StoredValue = cast<StoreInst>(I)->getValueOperand();
536
7
    // StoredValue may be a vector type if we are storing several vptrs at once.
537
7
    // In this case, just take the first element of the vector since this is
538
7
    // enough to find vptr races.
539
7
    if (isa<VectorType>(StoredValue->getType()))
540
1
      StoredValue = IRB.CreateExtractElement(
541
1
          StoredValue, ConstantInt::get(IRB.getInt32Ty(), 0));
542
7
    if (StoredValue->getType()->isIntegerTy())
543
1
      StoredValue = IRB.CreateIntToPtr(StoredValue, IRB.getInt8PtrTy());
544
7
    // Call TsanVptrUpdate.
545
7
    IRB.CreateCall(TsanVptrUpdate,
546
7
                   {IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()),
547
7
                    IRB.CreatePointerCast(StoredValue, IRB.getInt8PtrTy())});
548
7
    NumInstrumentedVtableWrites++;
549
7
    return true;
550
7
  }
551
62
  if (!IsWrite && 
isVtableAccess(I)42
) {
552
10
    IRB.CreateCall(TsanVptrLoad,
553
10
                   IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()));
554
10
    NumInstrumentedVtableReads++;
555
10
    return true;
556
10
  }
557
52
  const unsigned Alignment = IsWrite
558
52
      ? 
cast<StoreInst>(I)->getAlignment()20
559
52
      : 
cast<LoadInst>(I)->getAlignment()32
;
560
52
  Type *OrigTy = cast<PointerType>(Addr->getType())->getElementType();
561
52
  const uint32_t TypeSize = DL.getTypeStoreSizeInBits(OrigTy);
562
52
  FunctionCallee OnAccessFunc = nullptr;
563
52
  if (Alignment == 0 || 
Alignment >= 850
||
(Alignment % (TypeSize / 8)) == 036
)
564
44
    OnAccessFunc = IsWrite ? 
TsanWrite[Idx]16
:
TsanRead[Idx]28
;
565
8
  else
566
8
    OnAccessFunc = IsWrite ? 
TsanUnalignedWrite[Idx]4
:
TsanUnalignedRead[Idx]4
;
567
52
  IRB.CreateCall(OnAccessFunc, IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()));
568
52
  if (IsWrite) 
NumInstrumentedWrites++20
;
569
32
  else         NumInstrumentedReads++;
570
52
  return true;
571
52
}
572
573
284
static ConstantInt *createOrdering(IRBuilder<> *IRB, AtomicOrdering ord) {
574
284
  uint32_t v = 0;
575
284
  switch (ord) {
576
284
    case AtomicOrdering::NotAtomic:
577
0
      llvm_unreachable("unexpected atomic ordering!");
578
284
    
case AtomicOrdering::Unordered: 16
LLVM_FALLTHROUGH16
;
579
77
    case AtomicOrdering::Monotonic:              v = 0; break;
580
16
    // Not specified yet:
581
16
    // case AtomicOrdering::Consume:                v = 1; break;
582
57
    case AtomicOrdering::Acquire:                v = 2; break;
583
47
    case AtomicOrdering::Release:                v = 3; break;
584
42
    case AtomicOrdering::AcquireRelease:         v = 4; break;
585
61
    case AtomicOrdering::SequentiallyConsistent: v = 5; break;
586
284
  }
587
284
  return IRB->getInt32(v);
588
284
}
589
590
// If a memset intrinsic gets inlined by the code gen, we will miss races on it.
591
// So, we either need to ensure the intrinsic is not inlined, or instrument it.
592
// We do not instrument memset/memmove/memcpy intrinsics (too complicated),
593
// instead we simply replace them with regular function calls, which are then
594
// intercepted by the run-time.
595
// Since tsan is running after everyone else, the calls should not be
596
// replaced back with intrinsics. If that becomes wrong at some point,
597
// we will need to call e.g. __tsan_memset to avoid the intrinsics.
598
6
bool ThreadSanitizer::instrumentMemIntrinsic(Instruction *I) {
599
6
  IRBuilder<> IRB(I);
600
6
  if (MemSetInst *M = dyn_cast<MemSetInst>(I)) {
601
2
    IRB.CreateCall(
602
2
        MemsetFn,
603
2
        {IRB.CreatePointerCast(M->getArgOperand(0), IRB.getInt8PtrTy()),
604
2
         IRB.CreateIntCast(M->getArgOperand(1), IRB.getInt32Ty(), false),
605
2
         IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false)});
606
2
    I->eraseFromParent();
607
4
  } else if (MemTransferInst *M = dyn_cast<MemTransferInst>(I)) {
608
4
    IRB.CreateCall(
609
4
        isa<MemCpyInst>(M) ? 
MemcpyFn2
:
MemmoveFn2
,
610
4
        {IRB.CreatePointerCast(M->getArgOperand(0), IRB.getInt8PtrTy()),
611
4
         IRB.CreatePointerCast(M->getArgOperand(1), IRB.getInt8PtrTy()),
612
4
         IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false)});
613
4
    I->eraseFromParent();
614
4
  }
615
6
  return false;
616
6
}
617
618
// Both llvm and ThreadSanitizer atomic operations are based on C++11/C1x
619
// standards.  For background see C++11 standard.  A slightly older, publicly
620
// available draft of the standard (not entirely up-to-date, but close enough
621
// for casual browsing) is available here:
622
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf
623
// The following page contains more background information:
624
// http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/
625
626
258
bool ThreadSanitizer::instrumentAtomic(Instruction *I, const DataLayout &DL) {
627
258
  IRBuilder<> IRB(I);
628
258
  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
629
24
    Value *Addr = LI->getPointerOperand();
630
24
    int Idx = getMemoryAccessFuncIndex(Addr, DL);
631
24
    if (Idx < 0)
632
0
      return false;
633
24
    const unsigned ByteSize = 1U << Idx;
634
24
    const unsigned BitSize = ByteSize * 8;
635
24
    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
636
24
    Type *PtrTy = Ty->getPointerTo();
637
24
    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
638
24
                     createOrdering(&IRB, LI->getOrdering())};
639
24
    Type *OrigTy = cast<PointerType>(Addr->getType())->getElementType();
640
24
    Value *C = IRB.CreateCall(TsanAtomicLoad[Idx], Args);
641
24
    Value *Cast = IRB.CreateBitOrPointerCast(C, OrigTy);
642
24
    I->replaceAllUsesWith(Cast);
643
234
  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
644
24
    Value *Addr = SI->getPointerOperand();
645
24
    int Idx = getMemoryAccessFuncIndex(Addr, DL);
646
24
    if (Idx < 0)
647
0
      return false;
648
24
    const unsigned ByteSize = 1U << Idx;
649
24
    const unsigned BitSize = ByteSize * 8;
650
24
    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
651
24
    Type *PtrTy = Ty->getPointerTo();
652
24
    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
653
24
                     IRB.CreateBitOrPointerCast(SI->getValueOperand(), Ty),
654
24
                     createOrdering(&IRB, SI->getOrdering())};
655
24
    CallInst *C = CallInst::Create(TsanAtomicStore[Idx], Args);
656
24
    ReplaceInstWithInst(I, C);
657
210
  } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I)) {
658
176
    Value *Addr = RMWI->getPointerOperand();
659
176
    int Idx = getMemoryAccessFuncIndex(Addr, DL);
660
176
    if (Idx < 0)
661
0
      return false;
662
176
    FunctionCallee F = TsanAtomicRMW[RMWI->getOperation()][Idx];
663
176
    if (!F)
664
0
      return false;
665
176
    const unsigned ByteSize = 1U << Idx;
666
176
    const unsigned BitSize = ByteSize * 8;
667
176
    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
668
176
    Type *PtrTy = Ty->getPointerTo();
669
176
    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
670
176
                     IRB.CreateIntCast(RMWI->getValOperand(), Ty, false),
671
176
                     createOrdering(&IRB, RMWI->getOrdering())};
672
176
    CallInst *C = CallInst::Create(F, Args);
673
176
    ReplaceInstWithInst(I, C);
674
176
  } else 
if (AtomicCmpXchgInst *34
CASI34
= dyn_cast<AtomicCmpXchgInst>(I)) {
675
26
    Value *Addr = CASI->getPointerOperand();
676
26
    int Idx = getMemoryAccessFuncIndex(Addr, DL);
677
26
    if (Idx < 0)
678
0
      return false;
679
26
    const unsigned ByteSize = 1U << Idx;
680
26
    const unsigned BitSize = ByteSize * 8;
681
26
    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
682
26
    Type *PtrTy = Ty->getPointerTo();
683
26
    Value *CmpOperand =
684
26
      IRB.CreateBitOrPointerCast(CASI->getCompareOperand(), Ty);
685
26
    Value *NewOperand =
686
26
      IRB.CreateBitOrPointerCast(CASI->getNewValOperand(), Ty);
687
26
    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
688
26
                     CmpOperand,
689
26
                     NewOperand,
690
26
                     createOrdering(&IRB, CASI->getSuccessOrdering()),
691
26
                     createOrdering(&IRB, CASI->getFailureOrdering())};
692
26
    CallInst *C = IRB.CreateCall(TsanAtomicCAS[Idx], Args);
693
26
    Value *Success = IRB.CreateICmpEQ(C, CmpOperand);
694
26
    Value *OldVal = C;
695
26
    Type *OrigOldValTy = CASI->getNewValOperand()->getType();
696
26
    if (Ty != OrigOldValTy) {
697
1
      // The value is a pointer, so we need to cast the return value.
698
1
      OldVal = IRB.CreateIntToPtr(C, OrigOldValTy);
699
1
    }
700
26
701
26
    Value *Res =
702
26
      IRB.CreateInsertValue(UndefValue::get(CASI->getType()), OldVal, 0);
703
26
    Res = IRB.CreateInsertValue(Res, Success, 1);
704
26
705
26
    I->replaceAllUsesWith(Res);
706
26
    I->eraseFromParent();
707
26
  } else 
if (FenceInst *8
FI8
= dyn_cast<FenceInst>(I)) {
708
8
    Value *Args[] = {createOrdering(&IRB, FI->getOrdering())};
709
8
    FunctionCallee F = FI->getSyncScopeID() == SyncScope::SingleThread
710
8
                           ? 
TsanAtomicSignalFence4
711
8
                           : 
TsanAtomicThreadFence4
;
712
8
    CallInst *C = CallInst::Create(F, Args);
713
8
    ReplaceInstWithInst(I, C);
714
8
  }
715
258
  return true;
716
258
}
717
718
int ThreadSanitizer::getMemoryAccessFuncIndex(Value *Addr,
719
319
                                              const DataLayout &DL) {
720
319
  Type *OrigPtrTy = Addr->getType();
721
319
  Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType();
722
319
  assert(OrigTy->isSized());
723
319
  uint32_t TypeSize = DL.getTypeStoreSizeInBits(OrigTy);
724
319
  if (TypeSize != 8  && 
TypeSize != 16268
&&
725
319
      
TypeSize != 32218
&&
TypeSize != 64138
&&
TypeSize != 12855
) {
726
0
    NumAccessesWithBadSize++;
727
0
    // Ignore all unusual sizes.
728
0
    return -1;
729
0
  }
730
319
  size_t Idx = countTrailingZeros(TypeSize / 8);
731
319
  assert(Idx < kNumberOfAccessSizes);
732
319
  return Idx;
733
319
}