[SanitizerBinaryMetadata] Treat constant globals and non-escaping addresses specially

[melver]

Summary

For atomics metadata, we can make data race analysis more efficient by
entirely ignoring functions that include memory accesses but which only
access non-escaping (non-shared) and/or non-mutable memory. Such
functions will not be considered to be covered by "atomics" metadata,
resulting in the following benefits:

1. reduces "covered" metadata; and
2. allows data race analysis to skip such functions.

[dvyukov]

llvm/lib/Transforms/Instrumentation/SanitizerBinaryMetadata.cpp

383

What if we pretend these are atomic as well?

[melver]

llvm/lib/Transforms/Instrumentation/SanitizerBinaryMetadata.cpp

383

Marking things as atomic increases binary size. It's better to just not emit any metadata (less space used).

There are plenty function-local objects and if we mark all accesses to them as atomic, we'll end up with larger binaries.

Of course this will only help if all accesses in a function are non-escaping. If there's at least e.g. 1 global access, the function will end up being "covered" with atomics metadata again.

[dvyukov]

llvm/lib/Transforms/Instrumentation/SanitizerBinaryMetadata.cpp

383

But I think it's highly-likely a function also contains non-local accesses (esp for optimized builds with inlining where functions tend to be larger).
Maybe we should skip functions that contain only atomics accesses and local/non-interesting accesses (contains at least 1 interesting access).

[melver]

Make it more efficient by ignoring both non-shared and non-mutable addresses.

[melver]

PTAL.

Reworked some things to make it more efficient in the presence of constant data accesses.

llvm/lib/Transforms/Instrumentation/SanitizerBinaryMetadata.cpp

383

Changed it to look for shared+mutable.

So functions that access only non-escaping addresses and constant globals will be excluded entirely.

If a function is already covered by atomics metadata, constant globals will be considered atomic.

However, I think we still shouldn't pretend accesses to non-escaping memory are atomic because we'll increase binary size. Constant accesses should be relatively rare and can easily be optimized.

[dvyukov]

llvm/lib/Transforms/Instrumentation/SanitizerBinaryMetadata.cpp

383

Why this difference between global consts and non-escaping memory? Doesn't treating global consts as atomics also increase metadata size?
We marked coverage accesses as atomic to avoid "false" positives. But we don't need to do this for global consts.
If for non-escaping accesses it's profitable not mark them as atomics, shouldn't we do the same for global consts as well?

[melver]

Don't pretend constant accesses are atomic if the function is "covered", so save on space.

llvm/lib/Transforms/Instrumentation/SanitizerBinaryMetadata.cpp

383

Right, I think right now our biggest risk is binary size, so I'll change it to not add unnecessary atomics metadata.

llvm/lib/Transforms/Instrumentation/SanitizerBinaryMetadata.cpp

 
 #include "llvm/Transforms/Instrumentation/SanitizerBinaryMetadata.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/ADT/Twine.h"
+#include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
private:
 
   // Returns the section start marker name.
   Twine getSectionStart(StringRef SectionSuffix);
 
   // Returns the section end marker name.
   Twine getSectionEnd(StringRef SectionSuffix);
 
   // Returns true if the access to the address should be considered "atomic".
-  bool pretendAtomicAccess(Value *Addr);
+  bool pretendAtomicAccess(const Value *Addr);
 
   Module &Mod;
   const SanitizerBinaryMetadataOptions Options;
   const Triple TargetTriple;
   IRBuilder<> IRB;
 };
 
 bool SanitizerBinaryMetadata::run() {
bool useAfterReturnUnsafe(Instruction &I) {
   // Tail-called functions are not necessary intercepted
   // at runtime because there is no call instruction.
   // So conservatively mark the caller as requiring checking.
   else if (auto *CI = dyn_cast<CallInst>(&I))
     return CI->isTailCall() && !isUARSafeCall(CI);
   return false;
 }
 
-bool SanitizerBinaryMetadata::pretendAtomicAccess(Value *Addr) {
-  assert(Addr && "Expected non-null Addr");
+bool SanitizerBinaryMetadata::pretendAtomicAccess(const Value *Addr) {
+  if (!Addr)
+    return false;
 
   Addr = Addr->stripInBoundsOffsets();
   auto *GV = dyn_cast<GlobalVariable>(Addr);
   if (!GV)
     return false;
 
+  // Constant loads never race with writes.
+  if (GV->isConstant())
+    return true;
+
+  // Some compiler-generated accesses are known racy, to avoid false positives
+  // in data-race analysis pretend they're atomic.
   if (GV->hasSection()) {
     const auto OF = Triple(Mod.getTargetTriple()).getObjectFormat();
     const auto ProfSec =
         getInstrProfSectionName(IPSK_cnts, OF, /*AddSegmentInfo=*/false);
     if (GV->getSection().endswith(ProfSec))
       return true;
   }
-
   if (GV->getName().startswith("__llvm_gcov") ||
       GV->getName().startswith("__llvm_gcda"))
     return true;
 
   return false;
 }
 
+// Returns true if the memory at `Addr` may be shared with other threads.
+bool maybeSharedAddress(const Value *Addr) {
+  // By default assume memory may be shared.
+  if (!Addr)
+    return true;
+  if (isa<AllocaInst>(getUnderlyingObject(Addr)) &&
+      !PointerMayBeCaptured(Addr, true, true)) {
+    // The addressable object is on the stack and does not escape.
+    return false;
+  }
+  return true;
+}
+
 bool SanitizerBinaryMetadata::runOn(Instruction &I, MetadataInfoSet &MIS,
                                     MDBuilder &MDB, uint32_t &FeatureMask) {
   SmallVector<const MetadataInfo *, 1> InstMetadata;
   bool RequiresCovered = false;
 
   if (Options.UAR && !(FeatureMask & kSanitizerBinaryMetadataUAR)) {
     if (useAfterReturnUnsafe(I))
       FeatureMask |= kSanitizerBinaryMetadataUAR;
   }
 
-  if (Options.Atomics && I.mayReadOrWriteMemory()) {
-    auto SSID = getAtomicSyncScopeID(&I);
-    bool IsAtomic = SSID.has_value() && *SSID != SyncScope::SingleThread;
-
-    if (!IsAtomic) {
-      // Check to pretend some compiler-generated accesses are atomic, to avoid
-      // false positives in data-race analysis.
-      Value *Addr = nullptr;
-      if (auto *SI = dyn_cast<StoreInst>(&I))
-        Addr = SI->getPointerOperand();
-      else if (auto *LI = dyn_cast<LoadInst>(&I))
-        Addr = LI->getPointerOperand();
-      if (Addr)
-        IsAtomic = pretendAtomicAccess(Addr);
-    }
+  if (Options.Atomics) {
+    const Value *Addr = nullptr;
 
-    if (IsAtomic) {
+    if (I.mayReadOrWriteMemory() && maybeSharedAddress(Addr)) {
+      auto SSID = getAtomicSyncScopeID(&I);
+      if ((SSID.has_value() && *SSID != SyncScope::SingleThread) ||
+          pretendAtomicAccess(Addr)) {
         NumMetadataAtomics++;
         InstMetadata.push_back(&MetadataInfo::Atomics);
       }
       RequiresCovered = true;
     }
+  }
 
   // Attach MD_pcsections to instruction.
   if (!InstMetadata.empty()) {
     MIS.insert(InstMetadata.begin(), InstMetadata.end());
     SmallVector<MDBuilder::PCSection, 1> Sections;
     for (const auto &MI : InstMetadata)
       Sections.push_back({getSectionName(MI->SectionSuffix), {}});
     I.setMetadata(LLVMContext::MD_pcsections, MDB.createPCSections(Sections));

llvm/test/Instrumentation/SanitizerBinaryMetadata/pretend-atomic-access.ll

-; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature
 ; RUN: opt < %s -passes='module(sanmd-module)' -sanitizer-metadata-atomics -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"
 target triple = "x86_64-unknown-linux-gnu"
 
 @__profc_test_gep = private global [1 x i64] zeroinitializer, section "__llvm_prf_cnts", align 8
 @__profc_test_bitcast = private global [2 x i64] zeroinitializer, section "__llvm_prf_cnts", align 8
 @__profc_test_bitcast_foo = private global [1 x i64] zeroinitializer, section "__llvm_prf_cnts", align 8
 
 @__llvm_gcov_ctr = internal global [1 x i64] zeroinitializer
 @__llvm_gcov_ctr.1 = internal global [1 x i64] zeroinitializer
 @__llvm_gcov_global_state_pred = internal global i32 0
 @__llvm_gcda_foo = internal global i32 0
 
-define i32 @test_gep() sanitize_thread {
-; CHECK-LABEL: @test_gep(
+define i32 @test_gep() {
+; CHECK-LABEL: define {{[^@]+}}@test_gep() !pcsections !0 {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[PGOCOUNT:%.*]] = load i64, ptr @__profc_test_gep, align 8, !pcsections !2
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[PGOCOUNT]], 1
 ; CHECK-NEXT:    store i64 [[TMP0]], ptr @__profc_test_gep, align 8, !pcsections !2
 ; CHECK-NEXT:    [[GCOVCOUNT:%.*]] = load i64, ptr @__llvm_gcov_ctr, align 8, !pcsections !2
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[GCOVCOUNT]], 1
 ; CHECK-NEXT:    store i64 [[TMP1]], ptr @__llvm_gcov_ctr, align 8, !pcsections !2
 ; CHECK-NEXT:    [[GCOVCOUNT_1:%.*]] = load i64, ptr @__llvm_gcov_ctr.1, align 8, !pcsections !2
entry:
 
   %gcovcount.1 = load i64, ptr @__llvm_gcov_ctr.1
   %2 = add i64 %gcovcount.1, 1
   store i64 %2, ptr @__llvm_gcov_ctr.1
 
   ret i32 1
 }
 
-define i32 @test_bitcast() sanitize_thread {
-; CHECK-LABEL: @test_bitcast(
+define i32 @test_bitcast() {
+; CHECK-LABEL: define {{[^@]+}}@test_bitcast() !pcsections !0 {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load <2 x i64>, ptr @__profc_test_bitcast, align 8, !pcsections !2
 ; CHECK-NEXT:    [[DOTPROMOTED5:%.*]] = load i64, ptr @__profc_test_bitcast_foo, align 8, !pcsections !2
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[DOTPROMOTED5]], 10
 ; CHECK-NEXT:    [[TMP2:%.*]] = add <2 x i64> [[TMP0]], <i64 1, i64 10>
 ; CHECK-NEXT:    store <2 x i64> [[TMP2]], ptr @__profc_test_bitcast, align 8, !pcsections !2
 ; CHECK-NEXT:    store i64 [[TMP1]], ptr @__profc_test_bitcast_foo, align 8, !pcsections !2
 ; CHECK-NEXT:    ret i32 undef
 ;
 entry:
   %0 = load <2 x i64>, ptr @__profc_test_bitcast, align 8
   %.promoted5 = load i64, ptr @__profc_test_bitcast_foo, align 8
   %1 = add i64 %.promoted5, 10
   %2 = add <2 x i64> %0, <i64 1, i64 10>
   store <2 x i64> %2, ptr @__profc_test_bitcast, align 8
   store i64 %1, ptr @__profc_test_bitcast_foo, align 8
   ret i32 undef
 }
 
-define void @test_load() sanitize_thread {
-; CHECK-LABEL: @test_load(
+define void @test_load() {
+; CHECK-LABEL: define {{[^@]+}}@test_load() !pcsections !0 {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr @__llvm_gcov_global_state_pred, align 4, !pcsections !2
 ; CHECK-NEXT:    store i32 1, ptr @__llvm_gcov_global_state_pred, align 4, !pcsections !2
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, ptr @__llvm_gcda_foo, align 4, !pcsections !2
 ; CHECK-NEXT:    store i32 1, ptr @__llvm_gcda_foo, align 4, !pcsections !2
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %0 = load i32, ptr @__llvm_gcov_global_state_pred
   store i32 1, ptr @__llvm_gcov_global_state_pred
 
   %1 = load i32, ptr @__llvm_gcda_foo
   store i32 1, ptr @__llvm_gcda_foo
 
   ret void
 }
+
+@const_global = external constant i32
+define i32 @read_from_const_global() {
+; CHECK-LABEL: define {{[^@]+}}@read_from_const_global() !pcsections !0 {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr @const_global, align 4, !pcsections !2
+; CHECK-NEXT:    ret i32 [[TMP0]]
+;
+entry:
+  %0 = load i32, ptr @const_global, align 4
+  ret i32 %0
+}
+
+@non_const_global = global i32 0, align 4
+define i32 @read_from_non_const_global() {
+; CHECK-LABEL: define {{[^@]+}}@read_from_non_const_global() !pcsections !0 {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr @non_const_global, align 4
+; CHECK-NEXT:    ret i32 [[TMP0]]
+;
+entry:
+  %0 = load i32, ptr @non_const_global, align 4
+  ret i32 %0
+}
+
+@const_global_array = external constant [10 x i32]
+define i32 @read_from_const_global_array(i32 %idx) {
+; CHECK-LABEL: define {{[^@]+}}@read_from_const_global_array
+; CHECK-SAME: (i32 [[IDX:%.*]]) !pcsections !0 {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[IDX]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [10 x i32], ptr @const_global_array, i64 0, i64 [[IDXPROM]]
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4, !pcsections !2
+; CHECK-NEXT:    ret i32 [[TMP0]]
+;
+entry:
+  %idxprom = sext i32 %idx to i64
+  %arrayidx = getelementptr inbounds [10 x i32], ptr @const_global_array, i64 0, i64 %idxprom
+  %0 = load i32, ptr %arrayidx, align 4
+  ret i32 %0
+}

llvm/test/Instrumentation/SanitizerBinaryMetadata/shared-address.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature
+; RUN: opt < %s -passes='module(sanmd-module)' -sanitizer-metadata-atomics -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"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @escape(ptr)
+
+@sink = global ptr null, align 4
+
+@some_global = global i32 0, align 4
+
+define i32 @notcaptured() {
+; CHECK-LABEL: define {{[^@]+}}@notcaptured() {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PTR:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store i32 42, ptr [[PTR]], align 4
+; CHECK-NEXT:    [[TMP:%.*]] = load i32, ptr [[PTR]], align 4
+; CHECK-NEXT:    ret i32 [[TMP]]
+;
+entry:
+  %ptr = alloca i32, align 4
+  store i32 42, ptr %ptr, align 4
+  %tmp = load i32, ptr %ptr, align 4
+  ret i32 %tmp
+}
+
+define void @captured0() {
+; CHECK-LABEL: define {{[^@]+}}@captured0() !pcsections !0 {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PTR:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    call void @escape(ptr [[PTR]])
+; CHECK-NEXT:    store i32 42, ptr [[PTR]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %ptr = alloca i32, align 4
+  ; escapes due to call
+  call void @escape(ptr %ptr)
+  store i32 42, ptr %ptr, align 4
+  ret void
+}
+
+define void @captured1() {
+; CHECK-LABEL: define {{[^@]+}}@captured1() !pcsections !0 {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PTR:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store ptr [[PTR]], ptr @sink, align 8
+; CHECK-NEXT:    store i32 42, ptr [[PTR]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %ptr = alloca i32, align 4
+  ; escapes due to store into global
+  store ptr %ptr, ptr @sink, align 8
+  store i32 42, ptr %ptr, align 4
+  ret void
+}
+
+define void @captured2() {
+; CHECK-LABEL: define {{[^@]+}}@captured2() !pcsections !0 {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PTR:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[TMP:%.*]] = alloca ptr, align 8
+; CHECK-NEXT:    store ptr [[PTR]], ptr [[TMP]], align 8
+; CHECK-NEXT:    [[TMP0:%.*]] = load ptr, ptr [[TMP]], align 8
+; CHECK-NEXT:    store ptr [[TMP0]], ptr @sink, align 8
+; CHECK-NEXT:    store i32 42, ptr [[PTR]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %ptr = alloca i32, align 4
+  %tmp = alloca ptr, align 8
+  ; transitive escape
+  store ptr %ptr, ptr %tmp, align 8
+  %0 = load ptr, ptr %tmp, align 8
+  store ptr %0, ptr @sink, align 8
+  store i32 42, ptr %ptr, align 4
+  ret void
+}
+
+
+define i32 @notcaptured_and_global_access() {
+; CHECK-LABEL: define {{[^@]+}}@notcaptured_and_global_access() !pcsections !0 {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PTR:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[TMP:%.*]] = load i32, ptr @some_global, align 4
+; CHECK-NEXT:    store i32 42, ptr [[PTR]], align 4
+; CHECK-NEXT:    ret i32 [[TMP]]
+;
+entry:
+  %ptr = alloca i32, align 4
+  %tmp = load i32, ptr @some_global, align 4
+  store i32 42, ptr %ptr, align 4
+  ret i32 %tmp
+}