diff --git a/compiler-rt/test/msan/getaddrinfo.cpp b/compiler-rt/test/msan/getaddrinfo.cpp --- a/compiler-rt/test/msan/getaddrinfo.cpp +++ b/compiler-rt/test/msan/getaddrinfo.cpp @@ -7,6 +7,7 @@ void poison_stack_ahead() { char buf[100000]; + __asm__ volatile("" ::"r"(buf)); // With -O0 this poisons a large chunk of stack. } diff --git a/compiler-rt/test/msan/qsort.cpp b/compiler-rt/test/msan/qsort.cpp --- a/compiler-rt/test/msan/qsort.cpp +++ b/compiler-rt/test/msan/qsort.cpp @@ -19,6 +19,7 @@ void poison_stack_and_param() { char x[10000]; + __asm__ volatile("" ::"r"(x)); int y; dummy(y, y, y, y, y); } diff --git a/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp b/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp --- a/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp +++ b/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp @@ -145,6 +145,7 @@ #include "llvm/Transforms/Instrumentation/MemorySanitizer.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/BitVector.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallString.h" @@ -152,7 +153,10 @@ #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringRef.h" #include "llvm/ADT/Triple.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/MemoryLocation.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" @@ -496,7 +500,7 @@ MemorySanitizer(const MemorySanitizer &) = delete; MemorySanitizer &operator=(const MemorySanitizer &) = delete; - bool sanitizeFunction(Function &F, TargetLibraryInfo &TLI); + bool sanitizeFunction(Function &F, TargetLibraryInfo &TLI, AAResults *AA); private: friend struct MemorySanitizerVisitor; @@ -641,11 +645,13 @@ void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); + AU.addRequired(); } bool runOnFunction(Function &F) override { + AAResults *AA = &getAnalysis().getAAResults(); return MSan->sanitizeFunction( - F, getAnalysis().getTLI(F)); + F, getAnalysis().getTLI(F), AA); } bool doInitialization(Module &M) override; @@ -667,7 +673,8 @@ PreservedAnalyses MemorySanitizerPass::run(Function &F, FunctionAnalysisManager &FAM) { MemorySanitizer Msan(*F.getParent(), Options); - if (Msan.sanitizeFunction(F, FAM.getResult(F))) + AAResults &AA = FAM.getResult(F); + if (Msan.sanitizeFunction(F, FAM.getResult(F), &AA)) return PreservedAnalyses::none(); return PreservedAnalyses::all(); } @@ -686,6 +693,7 @@ "MemorySanitizer: detects uninitialized reads.", false, false) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_END(MemorySanitizerLegacyPass, "msan", "MemorySanitizer: detects uninitialized reads.", false, false) @@ -1056,6 +1064,7 @@ std::unique_ptr VAHelper; const TargetLibraryInfo *TLI; BasicBlock *ActualFnStart; + AAResults *AA; // The following flags disable parts of MSan instrumentation based on // exclusion list contents and command-line options. @@ -1079,8 +1088,9 @@ SmallVector StoreList; MemorySanitizerVisitor(Function &F, MemorySanitizer &MS, - const TargetLibraryInfo &TLI) - : F(F), MS(MS), VAHelper(CreateVarArgHelper(F, MS, *this)), TLI(&TLI) { + const TargetLibraryInfo &TLI, AAResults *AA) + : F(F), MS(MS), VAHelper(CreateVarArgHelper(F, MS, *this)), TLI(&TLI), + AA(AA) { bool SanitizeFunction = F.hasFnAttribute(Attribute::SanitizeMemory); InsertChecks = SanitizeFunction; PropagateShadow = SanitizeFunction; @@ -3832,6 +3842,77 @@ } } + // Bytes in an alloca already stored to + using StoredSet = BitVector; + // Mapping of Value modifying a pointer => Offset it's pointing to + using RedefOffsets = DenseMap; + // Set of instructions consuming a given alloca + using UserSet = SmallPtrSet; + + // Determine whether all paths from this alloca lead to storing into it. + // If true, we can omit poisoning the alloca because it'll just be + // overwritten anyway. + bool firstUsesAreStore(Value *Alloca, Instruction *CurrInst, + StoredSet StoredBytes) { + MemoryLocation AllocaLoc{Alloca, StoredBytes.size()}; + const DataLayout &DL = F.getParent()->getDataLayout(); + + for (; CurrInst && !StoredBytes.all(); + CurrInst = CurrInst->getNextNonDebugInstruction()) { + if (isNoModRef(AA->getModRefInfo(CurrInst, AllocaLoc))) + continue; + + if (StoreInst *Store = dyn_cast(CurrInst)) { + uint64_t StoreSize = + DL.getTypeStoreSize(Store->getValueOperand()->getType()); + // The store could be a use if it's storing the alloca + // pointer somewhere. But we don't want that. + Value *Ptr = Store->getPointerOperand(); + if (auto Offset = isPointerOffset(Alloca, Ptr, DL)) + StoredBytes.set(*Offset, *Offset + StoreSize); + continue; + } + + if (IntrinsicInst *Intrinsic = dyn_cast(CurrInst)) { + // Ignore lifetime intrinsics, count others as a use. + Intrinsic::ID ID = Intrinsic->getIntrinsicID(); + if (ID != Intrinsic::lifetime_start && ID != Intrinsic::lifetime_end) + return false; + continue; + } + + if (CallInst *Call = dyn_cast(CurrInst)) { + if (Call->getCalledFunction() != MS.MemcpyFn.getCallee() && + Call->getCalledFunction() != MS.MemsetFn.getCallee() && + Call->getCalledFunction() != MS.MemmoveFn.getCallee()) + // We want to consider instrumented memory writing functions + // as stores here. Anything else is considered a use. + return false; + + Value *StoreSizeVal = Call->getArgOperand(2); + Value *Dest = Call->getArgOperand(0); + auto Offset = isPointerOffset(Alloca, Dest, DL); + if (!Offset) + return false; + + ConstantInt *StoreSizeConst = dyn_cast(StoreSizeVal); + if (!StoreSizeConst) + // Can only decide this covers the whole shadow if we can + // check the constant store size. + return false; + uint64_t StoreSize = StoreSizeConst->getLimitedValue(); + StoredBytes.set(*Offset, *Offset + StoreSize); + continue; + } + + return false; + } + + // Reached end of basic block + // TODO: Check successive BBs + return StoredBytes.all(); + }; + void instrumentAlloca(AllocaInst &I, Instruction *InsPoint = nullptr) { if (!InsPoint) InsPoint = &I; @@ -3839,8 +3920,13 @@ const DataLayout &DL = F.getParent()->getDataLayout(); uint64_t TypeSize = DL.getTypeAllocSize(I.getAllocatedType()); Value *Len = ConstantInt::get(MS.IntptrTy, TypeSize); - if (I.isArrayAllocation()) + if (I.isArrayAllocation()) { Len = IRB.CreateMul(Len, I.getArraySize()); + } else { + StoredSet StoredBytes(TypeSize, false); + if (firstUsesAreStore(&I, InsPoint, StoredBytes)) + return; + } if (MS.CompileKernel) poisonAllocaKmsan(I, IRB, Len); @@ -5259,11 +5345,12 @@ return new VarArgNoOpHelper(Func, Msan, Visitor); } -bool MemorySanitizer::sanitizeFunction(Function &F, TargetLibraryInfo &TLI) { +bool MemorySanitizer::sanitizeFunction(Function &F, TargetLibraryInfo &TLI, + AAResults *AA) { if (!CompileKernel && F.getName() == kMsanModuleCtorName) return false; - MemorySanitizerVisitor Visitor(F, *this, TLI); + MemorySanitizerVisitor Visitor(F, *this, TLI, AA); // Clear out readonly/readnone attributes. AttrBuilder B; diff --git a/llvm/test/Instrumentation/MemorySanitizer/alloca-store.ll b/llvm/test/Instrumentation/MemorySanitizer/alloca-store.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Instrumentation/MemorySanitizer/alloca-store.ll @@ -0,0 +1,68 @@ +; Tests if MSAN can optimize away dead-code alloca poisons + +; RUN: opt < %s -msan-track-origins=2 -msan-check-access-address=0 -msan-poison-stack-with-call=1 -S -passes=msan 2>&1 | FileCheck \ +; RUN: %s "--check-prefixes=CHECK" + +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" + +define i32* @simple(i32 %val) sanitize_memory { + ; CHECK: define {{.*}} @simple + %p = alloca i32 + store i32 %val, i32* %p + ; CHECK-NOT: call void @__msan_poison_stack + ret i32* %p +} + +define i32* @bitcast({ i32 } %val) sanitize_memory { + ; CHECK: define {{.*}} @bitcast + %p = alloca i32 + %ps = bitcast i32* %p to { i32 }* + store { i32 } %val, { i32 }* %ps + ; CHECK-NOT: call void @__msan_poison_stack + ret i32* %p +} + +define i32* @lifetime(i32 %val) sanitize_memory { + ; CHECK: define {{.*}} @lifetime + %p = alloca i32 + %p8 = bitcast i32* %p to i8* + call void @llvm.lifetime.start(i64 4, i8* %p8) + store i32 %val, i32* %p + ; CHECK-NOT: call void @__msan_poison_stack + call void @llvm.lifetime.end(i64 4, i8* %p8) + ret i32* %p +} + +define i32* @with_memset(i8 %val) sanitize_memory { + ; CHECK: define {{.*}} @with_memset + %p = alloca i32 + %p8 = bitcast i32* %p to i8* + call void @llvm.memset(i8* %p8, i8 0, i64 4, i1 false) + ; CHECK-NOT: call void @__msan_poison_stack + ret i32* %p +} + +%struct.multi = type { i32, { i8, i8 }, i8, i8 } + +define i32* @piecemeal(i8 %val) sanitize_memory { + ; CHECK: define {{.*}} @piecemeal + %p = alloca %struct.multi + %p0 = getelementptr %struct.multi, %struct.multi* %p, i32 0, i32 0 + %p1 = getelementptr %struct.multi, %struct.multi* %p, i32 0, i32 1 + %p2 = getelementptr %struct.multi, %struct.multi* %p, i32 0, i32 2 + %p3 = getelementptr %struct.multi, %struct.multi* %p, i32 0, i32 3 + %p1_0 = getelementptr { i8, i8 }, { i8, i8 }* %p1, i32 0, i32 0 + %p1_1 = getelementptr { i8, i8 }, { i8, i8 }* %p1, i32 0, i32 1 + store i32 0, i32* %p0 + store i8 0, i8* %p1_0 + store i8 0, i8* %p1_1 + store i8 0, i8* %p2 + store i8 0, i8* %p3 + ; CHECK-NOT: call void @__msan_poison_stack + ret i32* %p0 +} + +declare void @llvm.memset(i8*, i8, i64, i1) +declare void @llvm.lifetime.start(i64, i8* nocapture) +declare void @llvm.lifetime.end(i64, i8* nocapture) diff --git a/llvm/test/Instrumentation/MemorySanitizer/alloca.ll b/llvm/test/Instrumentation/MemorySanitizer/alloca.ll --- a/llvm/test/Instrumentation/MemorySanitizer/alloca.ll +++ b/llvm/test/Instrumentation/MemorySanitizer/alloca.ll @@ -22,6 +22,7 @@ define void @static() sanitize_memory { entry: %x = alloca i32, align 4 + %y = ptrtoint i32* %x to i32 ret void } @@ -38,6 +39,7 @@ br label %l l: %x = alloca i32, align 4 + %y = ptrtoint i32* %x to i32 ret void } @@ -51,6 +53,7 @@ define void @array() sanitize_memory { entry: %x = alloca i32, i64 5, align 4 + %y = ptrtoint i32* %x to i32 ret void } @@ -64,6 +67,7 @@ define void @array_non_const(i64 %cnt) sanitize_memory { entry: %x = alloca i32, i64 %cnt, align 4 + %y = ptrtoint i32* %x to i32 ret void } @@ -79,6 +83,7 @@ define void @unpoison_local() { entry: %x = alloca i32, i64 5, align 4 + %y = ptrtoint i32* %x to i32 ret void } @@ -98,9 +103,11 @@ another_bb: call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %c) + %y = load i32, i32* %x store i32 7, i32* %x call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %c) call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %c) + %z = load i32, i32* %x store i32 8, i32* %x call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %c) ret void diff --git a/llvm/test/Instrumentation/MemorySanitizer/msan_x86_bts_asm.ll b/llvm/test/Instrumentation/MemorySanitizer/msan_x86_bts_asm.ll --- a/llvm/test/Instrumentation/MemorySanitizer/msan_x86_bts_asm.ll +++ b/llvm/test/Instrumentation/MemorySanitizer/msan_x86_bts_asm.ll @@ -58,9 +58,9 @@ ret i32 1 } -; %nr is first poisoned, then unpoisoned (written to). Need to optimize this in the future. -; CHECK: [[NRC1:%.*]] = bitcast i64* %nr to i8* -; CHECK: call void @__msan_poison_alloca(i8* [[NRC1]]{{.*}}) +; %nr is first poisoned, then unpoisoned (written to). No need to poison. +; CHECK-NOT: [[NRC1:%.*]] = bitcast i64* %nr to i8* +; CHECK-NOT: call void @__msan_poison_alloca(i8* [[NRC1]]{{.*}}) ; CHECK: [[NRC2:%.*]] = bitcast i64* %nr to i8* ; CHECK: call { i8*, i32* } @__msan_metadata_ptr_for_store_8(i8* [[NRC2]])