tsan: do not instrument not captured values

[dvyukov]

Summary

Consider the following code:

P p;
p.x = 1;
p.y = 2;
foo(&p);

P escapes and so tsan instruments accesses to it. However, before address of the variable is actually taken, it is not shared and so cannot participate in data races. So there is no point in instrumenting these initial memory accesses.

I've built some tests in WebRTC with and without this change. With this change number of __tsan_read/write calls is reduced by 20-40%, binary size decreases by 5-10% and execution time drops by ~5%. For example:

$ ls -l old/modules_unittests new/modules_unittests
-rwxr-x--- 1 dvyukov 41708976 Jan 20 18:35 old/modules_unittests
-rwxr-x--- 1 dvyukov 38294008 Jan 20 18:29 new/modules_unittests
$ objdump -d old/modules_unittests | egrep "callq.*tsan_(read|write|unaligned)" | wc -l
239871
$ objdump -d new/modules_unittests | egrep "callq.*tsan_(read|write|unaligned)" | wc -l
148365

[kcc]

Cool.
Do you have any numbers? (E.g. the %% of cases where it fires on SPEC)?

Two comments inlined

lib/Transforms/Instrumentation/ThreadSanitizer.cpp

341

Don't we want to reuse DT from previous passes, i.e. require it in getAnalysisUsage() ?

test/Instrumentation/ThreadSanitizer/capture.ll

18

CHECK-LABEL, here and below

[dvyukov]

Chandler, I've tested the approach where we ignore only completely non-captured variables, and it seems to give most of the benefit.
Number of __tsan_(read|write|unaligned) calls in webrtc modules_unittest was 240592; with my original patch -- 149078; with only PointerMayBeCaptured -- 149624.

Looks much simpler now as well. And also I don't need to figure out how to reuse DominatorTree from a previous pass :)

PTAL

[dvyukov]

Chandler, please take another look

[dvyukov]

Done

[kcc]

LGTM

This looks much nicer!
(Still, please give Chandler and chance to look)

[dvyukov]

Chandler, do you want to take another look? Otherwise I am submitting it.

[chandlerc]

Resigning as my memory is that we went with a different approach. If you need review here still, please add me back.

lib/Transforms/Instrumentation/ThreadSanitizer.cpp

 //
 // 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.
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"

 STATISTIC(NumOmittedReadsBeforeWrite,
           "Number of reads ignored due to following writes");
 STATISTIC(NumAccessesWithBadSize, "Number of accesses with bad size");
 STATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes");
 STATISTIC(NumInstrumentedVtableReads, "Number of vtable ptr reads");
 STATISTIC(NumOmittedReadsFromConstantGlobals,
           "Number of reads from constant globals");
 STATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads");
+STATISTIC(NumOmittedNonCaptured, "Number of accesses ignored due to capturing");
 
 namespace {
 
 /// ThreadSanitizer: instrument the code in module to find races.
 struct ThreadSanitizer : public FunctionPass {
   ThreadSanitizer() : FunctionPass(ID), DL(nullptr) {}
   const char *getPassName() const override;
   bool runOnFunction(Function &F) override;
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
     }
   }
   return false;
 }
 
 // Instrumenting some of the accesses may be proven redundant.
 // Currently handled:
 //  - read-before-write (within same BB, no calls between)
+//  - not captured variables
 //
 // We do not handle some of the patterns that should not survive
 // after the classic compiler optimizations.
 // E.g. two reads from the same temp should be eliminated by CSE,
 // two writes should be eliminated by DSE, etc.
 //
 // 'Local' is a vector of insns within the same BB (no calls between).
 // 'All' is a vector of insns that will be instrumented.
if (StoreInst *Store = dyn_cast<StoreInst>(I)) {
         NumOmittedReadsBeforeWrite++;
         continue;
       }
       if (addrPointsToConstantData(Addr)) {
         // Addr points to some constant data -- it can not race with any writes.
         continue;
       }
     }
+    Value *Addr = isa<StoreInst>(*I)
+        ? cast<StoreInst>(I)->getPointerOperand()
+        : cast<LoadInst>(I)->getPointerOperand();
+    if (isa<AllocaInst>(GetUnderlyingObject(Addr, nullptr)) &&
+        !PointerMayBeCaptured(Addr, true, true)) {
+      // The variable is addressable but not captured, so it cannot be
+      // referenced from a different thread and participate in a data race
+      // (see llvm/Analysis/CaptureTracking.h for details).
+      NumOmittedNonCaptured++;
+      continue;
+    }
     All.push_back(I);
   }
   Local.clear();
 }
 
 static bool isAtomic(Instruction *I) {
   if (LoadInst *LI = dyn_cast<LoadInst>(I))
     return LI->isAtomic() && LI->getSynchScope() == CrossThread;
bool ThreadSanitizer::runOnFunction(Function &F) {
   SmallVector<Instruction*, 8> LocalLoadsAndStores;
   SmallVector<Instruction*, 8> AtomicAccesses;
   SmallVector<Instruction*, 8> MemIntrinCalls;
   bool Res = false;
   bool HasCalls = false;
   bool SanitizeFunction = F.hasFnAttribute(Attribute::SanitizeThread);
 
   // Traverse all instructions, collect loads/stores/returns, check for calls.
   for (auto &BB : F) {
     for (auto &Inst : BB) {
       if (isAtomic(&Inst))
         AtomicAccesses.push_back(&Inst);
       else if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
         LocalLoadsAndStores.push_back(&Inst);
       else if (isa<ReturnInst>(Inst))
         RetVec.push_back(&Inst);
       else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {

test/Instrumentation/ThreadSanitizer/capture.ll

+; 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-S128"
+
+declare void @escape(i32*)
+
+@sink = global i32* null, align 4
+
+define void @captured0() nounwind uwtable sanitize_thread {
+entry:
+  %ptr = alloca i32, align 4
+  ; escapes due to call
+  call void @escape(i32* %ptr)
+  store i32 42, i32* %ptr, align 4
+  ret void
+}
+; CHECK-LABEL: define void @captured0
+; CHECK: __tsan_write
+; CHECK: ret void
+
+define void @captured1() nounwind uwtable sanitize_thread {
+entry:
+  %ptr = alloca i32, align 4
+  ; escapes due to store into global
+  store i32* %ptr, i32** @sink, align 4
+  store i32 42, i32* %ptr, align 4
+  ret void
+}
+; CHECK-LABEL: define void @captured1
+; CHECK: __tsan_write
+; CHECK: __tsan_write
+; CHECK: ret void
+
+define void @captured2() nounwind uwtable sanitize_thread {
+entry:
+  %ptr = alloca i32, align 4
+  %tmp = alloca i32*, align 8
+  ; transitive escape
+  store i32* %ptr, i32** %tmp, align 8
+  %0 = load i32** %tmp, align 8
+  store i32* %0, i32** @sink, align 8
+  store i32 42, i32* %ptr, align 4
+  ret void
+}
+; CHECK-LABEL: define void @captured2
+; CHECK: __tsan_write
+; CHECK: __tsan_write
+; CHECK: ret void
+
+define void @notcaptured0() nounwind uwtable sanitize_thread {
+entry:
+  %ptr = alloca i32, align 4
+  store i32 42, i32* %ptr, align 4
+  ; escapes due to call
+  call void @escape(i32* %ptr)
+  ret void
+}
+; CHECK-LABEL: define void @notcaptured0
+; CHECK: __tsan_write
+; CHECK: ret void
+
+define void @notcaptured1() nounwind uwtable sanitize_thread {
+entry:
+  %ptr = alloca i32, align 4
+  store i32 42, i32* %ptr, align 4
+  ; escapes due to store into global
+  store i32* %ptr, i32** @sink, align 4
+  ret void
+}
+; CHECK-LABEL: define void @notcaptured1
+; CHECK: __tsan_write
+; CHECK: __tsan_write
+; CHECK: ret void
+
+define void @notcaptured2() nounwind uwtable sanitize_thread {
+entry:
+  %ptr = alloca i32, align 4
+  %tmp = alloca i32*, align 8
+  store i32 42, i32* %ptr, align 4
+  ; transitive escape
+  store i32* %ptr, i32** %tmp, align 8
+  %0 = load i32** %tmp, align 8
+  store i32* %0, i32** @sink, align 8
+  ret void
+}
+; CHECK-LABEL: define void @notcaptured2
+; CHECK: __tsan_write
+; CHECK: __tsan_write
+; CHECK: ret void
+
+