[sanitizers] Invalidate GlobalsAA

[vitalybuka]

Summary

GlobalsAA is considered stateless as usually transformations do not introduce
new global accesses, and removed global access is not a problem for GlobalsAA
users.
Sanitizers introduce new global accesses:

• Msan and Dfsan tracks origins and parameters with TLS, and to store stack origins.
  • Sancov uses global counters. HWAsan store tag state in TLS.
  • Asan modifies globals, but I am not sure if invalidation is required.

I see no evidence that TSan needs invalidation.

[aeubanks]

Mentioning in the summary that GlobalsAA only expects simplification and therefore doesn't expect new globals (as I understand). Also that GlobalsAA is special in the way it's invalidated/updated.
I'd like somebody like @asbirlea to confirm this.

llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp

3374

adding comments here would be helpful

[asbirlea]

Confirming this is necessary - the patch came after an offline discussion of the issue.
+1 to adding comments to explain why this is needed: GlobalsAA is considered stateless and does not get invalidated unless explicitly invalidated; PreservedAnalyses::none() is not enough. Sanitizers make changes that require GlobalsAA to be invalidated.

[aeubanks]

also it would be nice to have some sort of check to detect this sort of issue with GlobalsAA and instrumentation passes, perhaps gated under expensive checks. haven't thought too hard on how that would work

[vitalybuka]

In D133394#3777688, @aeubanks wrote:

also it would be nice to have some sort of check to detect this sort of issue with GlobalsAA and instrumentation passes, perhaps gated under expensive checks. haven't thought too hard on how that would work

I assume not in this patch?

[vitalybuka]

comments

[aeubanks]

In D133394#3777909, @vitalybuka wrote:

In D133394#3777688, @aeubanks wrote:

also it would be nice to have some sort of check to detect this sort of issue with GlobalsAA and instrumentation passes, perhaps gated under expensive checks. haven't thought too hard on how that would work

I assume not in this patch?

yeah not here, I'm just randomly throwing out ideas

llvm/test/Instrumentation/MemorySanitizer/msan_invalidate.ll

8

if possible could you reduce this test case? e.g. dso_local/target datalayout/triple/lifetime/noundef

[vitalybuka]

simplify tests

llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp

 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/ADT/Twine.h"
+#include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/StackSafetyAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Demangle/Demangle.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
PreservedAnalyses AddressSanitizerPass::run(Module &M,
   for (Function &F : M) {
     AddressSanitizer FunctionSanitizer(M, SSGI, Options.CompileKernel,
                                        Options.Recover, Options.UseAfterScope,
                                        Options.UseAfterReturn);
     const TargetLibraryInfo &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
     Modified |= FunctionSanitizer.instrumentFunction(F, &TLI);
   }
   Modified |= ModuleSanitizer.instrumentModule(M);
-  return Modified ? PreservedAnalyses::none() : PreservedAnalyses::all();
+  if (!Modified)
+    return PreservedAnalyses::all();
+
+  PreservedAnalyses PA = PreservedAnalyses::none();
+  PA.abandon<GlobalsAA>();
+  return PA;
 }
 
 static size_t TypeSizeToSizeIndex(uint32_t TypeSize) {
   size_t Res = countTrailingZeros(TypeSize / 8);
   assert(Res < kNumberOfAccessSizes);
   return Res;
 }
 

llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp

 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/ADT/iterator.h"
+#include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"

 
 ModulePass *llvm::createDataFlowSanitizerLegacyPassPass(
     const std::vector<std::string> &ABIListFiles) {
   return new DataFlowSanitizerLegacyPass(ABIListFiles);
 }
 
 PreservedAnalyses DataFlowSanitizerPass::run(Module &M,
                                              ModuleAnalysisManager &AM) {
-  if (DataFlowSanitizer(ABIListFiles).runImpl(M, &AM)) {
-    return PreservedAnalyses::none();
-  }
+  if (!DataFlowSanitizer(ABIListFiles).runImpl(M, &AM))
     return PreservedAnalyses::all();
+
+  PreservedAnalyses PA = PreservedAnalyses::none();
+  PA.abandon<GlobalsAA>();
+  return PA;
 }

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp

 
 #include "llvm/Transforms/Instrumentation/HWAddressSanitizer.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
+#include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/StackSafetyAnalysis.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
PreservedAnalyses HWAddressSanitizerPass::run(Module &M,
   if (shouldUseStackSafetyAnalysis(TargetTriple, Options.DisableOptimization))
     SSI = &MAM.getResult<StackSafetyGlobalAnalysis>(M);
 
   HWAddressSanitizer HWASan(M, Options.CompileKernel, Options.Recover, SSI);
   bool Modified = false;
   auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
   for (Function &F : M)
     Modified |= HWASan.sanitizeFunction(F, FAM);
-  if (Modified)
-    return PreservedAnalyses::none();
+  if (!Modified)
     return PreservedAnalyses::all();
+
+  PreservedAnalyses PA = PreservedAnalyses::none();
+  PA.abandon<GlobalsAA>();
+  return PA;
 }
 void HWAddressSanitizerPass::printPipeline(
     raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
   static_cast<PassInfoMixin<HWAddressSanitizerPass> *>(this)->printPipeline(
       OS, MapClassName2PassName);
   OS << "<";
   if (Options.CompileKernel)
     OS << "kernel;";

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
+#include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
PreservedAnalyses ModuleMemorySanitizerPass::run(Module &M,
   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
   for (Function &F : M) {
     if (F.empty())
       continue;
     MemorySanitizer Msan(*F.getParent(), Options);
     Modified |=
         Msan.sanitizeFunction(F, FAM.getResult<TargetLibraryAnalysis>(F));
   }
-  return Modified ? PreservedAnalyses::none() : PreservedAnalyses::all();
+
+  if (!Modified)
+    return PreservedAnalyses::all();
+
+  PreservedAnalyses PA = PreservedAnalyses::none();
+  PA.abandon<GlobalsAA>();
+  return PA;
 }
 
 void ModuleMemorySanitizerPass::printPipeline(
     raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
   static_cast<PassInfoMixin<ModuleMemorySanitizerPass> *>(this)->printPipeline(
       OS, MapClassName2PassName);
   OS << "<";
   if (Options.Recover)

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Instrumentation/SanitizerCoverage.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Analysis/EHPersonalities.h"
+#include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/IntrinsicInst.h"
ModuleSanitizerCoverage ModuleSancov(Options, Allowlist.get(),
                                        Blocklist.get());
   auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
   auto DTCallback = [&FAM](Function &F) -> const DominatorTree * {
     return &FAM.getResult<DominatorTreeAnalysis>(F);
   };
   auto PDTCallback = [&FAM](Function &F) -> const PostDominatorTree * {
     return &FAM.getResult<PostDominatorTreeAnalysis>(F);
   };
-  if (ModuleSancov.instrumentModule(M, DTCallback, PDTCallback))
-    return PreservedAnalyses::none();
+  if (!ModuleSancov.instrumentModule(M, DTCallback, PDTCallback))
     return PreservedAnalyses::all();
+
+  PreservedAnalyses PA = PreservedAnalyses::none();
+  PA.abandon<GlobalsAA>();
+  return PA;
 }
 
 std::pair<Value *, Value *>
 ModuleSanitizerCoverage::CreateSecStartEnd(Module &M, const char *Section,
                                            Type *Ty) {
   // Use ExternalWeak so that if all sections are discarded due to section
   // garbage collection, the linker will not report undefined symbol errors.
   // Windows defines the start/stop symbols in compiler-rt so no need for

llvm/test/Instrumentation/MemorySanitizer/invalidate_global_aa.ll

+; Check that sanitizers invalidate GlobalsAA
+
+; Msan and Dfsan use globals for origin tracking and TLS for parameters.
+; RUN: opt < %s -S -passes='require<globals-aa>,module(msan)' -debug-pass-manager 2>&1 | FileCheck %s
+; RUN: opt < %s -S -passes='require<globals-aa>,module(dfsan)' -debug-pass-manager 2>&1 | FileCheck %s
+
+; Some types of coverage use globals.
+; RUN: opt < %s -S -passes='require<globals-aa>,module(sancov-module)' -sanitizer-coverage-level=2 -debug-pass-manager 2>&1 | FileCheck %s
+
+; Uses TLS for tags.
+; RUN: opt < %s -S -passes='require<globals-aa>,module(hwasan)' -debug-pass-manager 2>&1 | FileCheck %s
+
+; Modifies globals.
+; RUN: opt < %s -S -passes='require<globals-aa>,module(asan)' -debug-pass-manager 2>&1 | FileCheck %s
+
+; CHECK: Running analysis: GlobalsAA on [module]
+; CHECK: Running pass: {{.*}}Sanitizer{{.*}}Pass on [module]
+; CHECK: Invalidating analysis: GlobalsAA on [module]
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define dso_local noundef ptr @_Z10max_by_ptrPiS_(ptr noundef readonly %a, ptr noundef readonly %b) local_unnamed_addr sanitize_address sanitize_hwaddress {
+entry:
+  %0 = load i32, ptr %a, align 4
+  %1 = load i32, ptr %b, align 4
+  %cmp = icmp slt i32 %0, %1
+  %cond = select i1 %cmp, ptr %b, ptr %a
+  ret ptr %cond
+}

llvm/test/Instrumentation/MemorySanitizer/msan_invalidate.ll

+; Regression test for msan not invalidating GlobalsAA.
+; RUN: opt < %s -S -passes='require<globals-aa>,module(msan),require<globals-aa>,early-cse<memssa>' 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define dso_local noundef ptr @_Z10max_by_ptrPiS_(ptr noundef readonly %a, ptr noundef readonly %b) local_unnamed_addr sanitize_memory {
+entry:
+  %0 = load i32, ptr %a, align 4
+  %1 = load i32, ptr %b, align 4
+  %cmp = icmp slt i32 %0, %1
+  %cond = select i1 %cmp, ptr %b, ptr %a
+  ret ptr %cond
+}
+
+define dso_local noundef i32 @main() local_unnamed_addr sanitize_memory {
+entry:
+  ; CHECK-LABEL: define dso_local noundef i32 @main()
+  ; CHECK: store i64 0, ptr @__msan_retval_tls, align 8
+  ; CHECK-NEXT: call noundef ptr @_Z10max_by_ptrPiS_(ptr noundef %px.0.px.0.px.0., ptr noundef nonnull %y)
+  ; If GlobalsAA is eliminated correctly, early-cse should not remove next load.
+  ; CHECK-NEXT: %[[MSRET:.*]] = load i64, ptr @__msan_retval_tls, align 8
+  ; CHECK-NEXT: %[[MSCMP:.*]] = icmp ne i64 %[[MSRET]], 0
+  ; CHECK-NEXT: br i1 %[[MSCMP]],
+
+  %x = alloca i32, align 4
+  %px = alloca ptr, align 8
+  %y = alloca i32, align 4
+  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %x)
+  call void @llvm.lifetime.start.p0(i64 8, ptr nonnull %px)
+  store volatile ptr %x, ptr %px, align 8
+  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %y)
+  store i32 43, ptr %y, align 4
+  %px.0.px.0.px.0. = load volatile ptr, ptr %px, align 8
+  %call = call noundef ptr @_Z10max_by_ptrPiS_(ptr noundef %px.0.px.0.px.0., ptr noundef nonnull %y)
+  %0 = load i32, ptr %call, align 4
+  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %y)
+  call void @llvm.lifetime.end.p0(i64 8, ptr nonnull %px)
+  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %x)
+  ret i32 %0
+}
+
+declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture)
+
+declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture)