From fac8403249ff180c2d2566b5b6476d1e9d588a8b Mon Sep 17 00:00:00 2001 From: Evgeniy Stepanov Date: Fri, 25 Jan 2013 15:31:10 +0000 Subject: [PATCH] [msan] Implement exact shadow propagation for relational ICmp. Only for integers, pointers, and vectors of those. No floats. Instrumentation seems very heavy, and may need to be replaced with some approximation in the future. llvm-svn: 173452 --- .../Transforms/Instrumentation/MemorySanitizer.cpp | 70 ++++++++++++++++++++++ .../Instrumentation/MemorySanitizer/msan_basic.ll | 34 ++++++++++- 2 files changed, 101 insertions(+), 3 deletions(-) diff --git a/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp b/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp index 40f0ebb..64882c2 100644 --- a/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp +++ b/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp @@ -127,6 +127,10 @@ static cl::opt ClHandleICmp("msan-handle-icmp", cl::desc("propagate shadow through ICmpEQ and ICmpNE"), cl::Hidden, cl::init(true)); +static cl::opt ClHandleICmpExact("msan-handle-icmp-exact", + cl::desc("exact handling of relational integer ICmp"), + cl::Hidden, cl::init(true)); + static cl::opt ClStoreCleanOrigin("msan-store-clean-origin", cl::desc("store origin for clean (fully initialized) values"), cl::Hidden, cl::init(false)); @@ -1155,6 +1159,70 @@ struct MemorySanitizerVisitor : public InstVisitor { setOriginForNaryOp(I); } + /// \brief Build the lowest possible value of V, taking into account V's + /// uninitialized bits. + Value *getLowestPossibleValue(IRBuilder<> &IRB, Value *A, Value *Sa, + bool isSigned) { + if (isSigned) { + // Split shadow into sign bit and other bits. + Value *SaOtherBits = IRB.CreateLShr(IRB.CreateShl(Sa, 1), 1); + Value *SaSignBit = IRB.CreateXor(Sa, SaOtherBits); + // Maximise the undefined shadow bit, minimize other undefined bits. + return + IRB.CreateOr(IRB.CreateAnd(A, IRB.CreateNot(SaOtherBits)), SaSignBit); + } else { + // Minimize undefined bits. + return IRB.CreateAnd(A, IRB.CreateNot(Sa)); + } + } + + /// \brief Build the highest possible value of V, taking into account V's + /// uninitialized bits. + Value *getHighestPossibleValue(IRBuilder<> &IRB, Value *A, Value *Sa, + bool isSigned) { + if (isSigned) { + // Split shadow into sign bit and other bits. + Value *SaOtherBits = IRB.CreateLShr(IRB.CreateShl(Sa, 1), 1); + Value *SaSignBit = IRB.CreateXor(Sa, SaOtherBits); + // Minimise the undefined shadow bit, maximise other undefined bits. + return + IRB.CreateOr(IRB.CreateAnd(A, IRB.CreateNot(SaSignBit)), SaOtherBits); + } else { + // Maximize undefined bits. + return IRB.CreateOr(A, Sa); + } + } + + /// \brief Instrument relational comparisons. + /// + /// This function does exact shadow propagation for all relational + /// comparisons of integers, pointers and vectors of those. + /// FIXME: output seems suboptimal when one of the operands is a constant + void handleRelationalComparisonExact(ICmpInst &I) { + IRBuilder<> IRB(&I); + Value *A = I.getOperand(0); + Value *B = I.getOperand(1); + Value *Sa = getShadow(A); + Value *Sb = getShadow(B); + + // Get rid of pointers and vectors of pointers. + // For ints (and vectors of ints), types of A and Sa match, + // and this is a no-op. + A = IRB.CreatePointerCast(A, Sa->getType()); + B = IRB.CreatePointerCast(B, Sb->getType()); + + bool IsSigned = I.isSigned(); + Value *S1 = IRB.CreateICmp(I.getPredicate(), + getLowestPossibleValue(IRB, A, Sa, IsSigned), + getHighestPossibleValue(IRB, B, Sb, IsSigned)); + Value *S2 = IRB.CreateICmp(I.getPredicate(), + getHighestPossibleValue(IRB, A, Sa, IsSigned), + getLowestPossibleValue(IRB, B, Sb, IsSigned)); + Value *Si = IRB.CreateXor(S1, S2); + setShadow(&I, Si); + setOriginForNaryOp(I); + } + /// \brief Instrument signed relational comparisons. /// /// Handle (x<0) and (x>=0) comparisons (essentially, sign bit tests) by @@ -1186,6 +1254,8 @@ struct MemorySanitizerVisitor : public InstVisitor { void visitICmpInst(ICmpInst &I) { if (ClHandleICmp && I.isEquality()) handleEqualityComparison(I); + else if (ClHandleICmp && ClHandleICmpExact && I.isRelational()) + handleRelationalComparisonExact(I); else if (ClHandleICmp && I.isSigned() && I.isRelational()) handleSignedRelationalComparison(I); else diff --git a/llvm/test/Instrumentation/MemorySanitizer/msan_basic.ll b/llvm/test/Instrumentation/MemorySanitizer/msan_basic.ll index a3caa80..16453c5 100644 --- a/llvm/test/Instrumentation/MemorySanitizer/msan_basic.ll +++ b/llvm/test/Instrumentation/MemorySanitizer/msan_basic.ll @@ -323,6 +323,8 @@ define zeroext i1 @ICmpSLT(i32 %x) nounwind uwtable readnone { ; CHECK-NOT: call void @__msan_warning ; CHECK: icmp slt ; CHECK-NOT: call void @__msan_warning +; CHECK: icmp slt +; CHECK-NOT: call void @__msan_warning ; CHECK: ret i1 define zeroext i1 @ICmpSGE(i32 %x) nounwind uwtable readnone { @@ -331,7 +333,9 @@ define zeroext i1 @ICmpSGE(i32 %x) nounwind uwtable readnone { } ; CHECK: @ICmpSGE -; CHECK: icmp slt +; CHECK: icmp sge +; CHECK-NOT: call void @__msan_warning +; CHECK: icmp sge ; CHECK-NOT: call void @__msan_warning ; CHECK: icmp sge ; CHECK-NOT: call void @__msan_warning @@ -343,7 +347,9 @@ define zeroext i1 @ICmpSGT(i32 %x) nounwind uwtable readnone { } ; CHECK: @ICmpSGT -; CHECK: icmp slt +; CHECK: icmp sgt +; CHECK-NOT: call void @__msan_warning +; CHECK: icmp sgt ; CHECK-NOT: call void @__msan_warning ; CHECK: icmp sgt ; CHECK-NOT: call void @__msan_warning @@ -355,7 +361,9 @@ define zeroext i1 @ICmpSLE(i32 %x) nounwind uwtable readnone { } ; CHECK: @ICmpSLE -; CHECK: icmp slt +; CHECK: icmp sle +; CHECK-NOT: call void @__msan_warning +; CHECK: icmp sle ; CHECK-NOT: call void @__msan_warning ; CHECK: icmp sle ; CHECK-NOT: call void @__msan_warning @@ -373,11 +381,31 @@ define <2 x i1> @ICmpSLT_vector(<2 x i32*> %x) nounwind uwtable readnone { ; CHECK: @ICmpSLT_vector ; CHECK: icmp slt <2 x i64> ; CHECK-NOT: call void @__msan_warning +; CHECK: icmp slt <2 x i64> +; CHECK-NOT: call void @__msan_warning ; CHECK: icmp slt <2 x i32*> ; CHECK-NOT: call void @__msan_warning ; CHECK: ret <2 x i1> +; Check that we propagate shadow for arbitrary relational comparisons + +define zeroext i1 @ICmpSLENonZero(i32 %x, i32 %y) nounwind uwtable readnone { +entry: + %cmp = icmp sle i32 %x, %y + ret i1 %cmp +} + +; CHECK: @ICmpSLENonZero +; CHECK: icmp sle i32 +; CHECK-NOT: call void @__msan_warning +; CHECK: icmp sle i32 +; CHECK-NOT: call void @__msan_warning +; CHECK: icmp sle i32 +; CHECK-NOT: call void @__msan_warning +; CHECK: ret i1 + + ; Check that loads of shadow have the same aligment as the original loads. ; Check that loads of origin have the aligment of max(4, original alignment). -- 2.7.4