From e0134d95cc14a040592e5d07ff14c4619e50a071 Mon Sep 17 00:00:00 2001 From: David Majnemer Date: Tue, 19 Aug 2014 23:36:30 +0000 Subject: [PATCH] InstCombine: Annotate sub with nsw when we prove it's safe We can prove that a 'sub' can be a 'sub nsw' under certain conditions: - The sign bits of the operands is the same. - Both operands have more than 1 sign bit. The subtraction cannot be a signed overflow in either case. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@216037 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombine.h | 1 + lib/Transforms/InstCombine/InstCombineAddSub.cpp | 40 +++++++++++++++++++++++- test/Transforms/InstCombine/memcmp-1.ll | 2 +- test/Transforms/InstCombine/strcmp-1.ll | 2 +- test/Transforms/InstCombine/strncmp-1.ll | 4 +-- test/Transforms/InstCombine/sub-xor.ll | 2 +- test/Transforms/InstCombine/sub.ll | 36 +++++++++++++++++++++ 7 files changed, 81 insertions(+), 6 deletions(-) diff --git a/lib/Transforms/InstCombine/InstCombine.h b/lib/Transforms/InstCombine/InstCombine.h index 623f25db068..8cb634c8a3e 100644 --- a/lib/Transforms/InstCombine/InstCombine.h +++ b/lib/Transforms/InstCombine/InstCombine.h @@ -250,6 +250,7 @@ private: Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI); bool WillNotOverflowSignedAdd(Value *LHS, Value *RHS); bool WillNotOverflowUnsignedAdd(Value *LHS, Value *RHS); + bool WillNotOverflowSignedSub(Value *LHS, Value *RHS); Value *EmitGEPOffset(User *GEP); Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN); Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef Mask); diff --git a/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/lib/Transforms/InstCombine/InstCombineAddSub.cpp index 22cc34d861a..22566ceb050 100644 --- a/lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ b/lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -956,6 +956,38 @@ bool InstCombiner::WillNotOverflowUnsignedAdd(Value *LHS, Value *RHS) { return false; } +/// \brief Return true if we can prove that: +/// (sub LHS, RHS) === (sub nsw LHS, RHS) +/// This basically requires proving that the add in the original type would not +/// overflow to change the sign bit or have a carry out. +/// TODO: Handle this for Vectors. +bool InstCombiner::WillNotOverflowSignedSub(Value *LHS, Value *RHS) { + // If LHS and RHS each have at least two sign bits, the subtraction + // cannot overflow. + if (ComputeNumSignBits(LHS) > 1 && ComputeNumSignBits(RHS) > 1) + return true; + + if (IntegerType *IT = dyn_cast(LHS->getType())) { + unsigned BitWidth = IT->getBitWidth(); + APInt LHSKnownZero(BitWidth, 0); + APInt LHSKnownOne(BitWidth, 0); + computeKnownBits(LHS, LHSKnownZero, LHSKnownOne); + + APInt RHSKnownZero(BitWidth, 0); + APInt RHSKnownOne(BitWidth, 0); + computeKnownBits(RHS, RHSKnownZero, RHSKnownOne); + + // Subtraction of two 2's compliment numbers having identical signs will + // never overflow. + if ((LHSKnownOne[BitWidth - 1] && RHSKnownOne[BitWidth - 1]) || + (LHSKnownZero[BitWidth - 1] && RHSKnownZero[BitWidth - 1])) + return true; + + // TODO: implement logic similar to checkRippleForAdd + } + return false; +} + // Checks if any operand is negative and we can convert add to sub. // This function checks for following negative patterns // ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C)) @@ -1623,7 +1655,13 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) { return ReplaceInstUsesWith(I, Res); } - return nullptr; + bool Changed = false; + if (!I.hasNoSignedWrap() && WillNotOverflowSignedSub(Op0, Op1)) { + Changed = true; + I.setHasNoSignedWrap(true); + } + + return Changed ? &I : nullptr; } Instruction *InstCombiner::visitFSub(BinaryOperator &I) { diff --git a/test/Transforms/InstCombine/memcmp-1.ll b/test/Transforms/InstCombine/memcmp-1.ll index 65349c6e690..d960693a05d 100644 --- a/test/Transforms/InstCombine/memcmp-1.ll +++ b/test/Transforms/InstCombine/memcmp-1.ll @@ -37,7 +37,7 @@ define i32 @test_simplify3(i8* %mem1, i8* %mem2) { ; CHECK: [[ZEXT1:%[a-z]+]] = zext i8 [[LOAD1]] to i32 ; CHECK: [[LOAD2:%[a-z]+]] = load i8* %mem2, align 1 ; CHECK: [[ZEXT2:%[a-z]+]] = zext i8 [[LOAD2]] to i32 -; CHECK: [[RET:%[a-z]+]] = sub i32 [[ZEXT1]], [[ZEXT2]] +; CHECK: [[RET:%[a-z]+]] = sub nsw i32 [[ZEXT1]], [[ZEXT2]] ret i32 %ret ; CHECK: ret i32 [[RET]] } diff --git a/test/Transforms/InstCombine/strcmp-1.ll b/test/Transforms/InstCombine/strcmp-1.ll index fc58ffcb8cb..9bbd7dbe7da 100644 --- a/test/Transforms/InstCombine/strcmp-1.ll +++ b/test/Transforms/InstCombine/strcmp-1.ll @@ -15,7 +15,7 @@ define i32 @test1(i8* %str2) { ; CHECK-LABEL: @test1( ; CHECK: %strcmpload = load i8* %str ; CHECK: %1 = zext i8 %strcmpload to i32 -; CHECK: %2 = sub i32 0, %1 +; CHECK: %2 = sub nsw i32 0, %1 ; CHECK: ret i32 %2 %str1 = getelementptr inbounds [1 x i8]* @null, i32 0, i32 0 diff --git a/test/Transforms/InstCombine/strncmp-1.ll b/test/Transforms/InstCombine/strncmp-1.ll index df30dd10044..49b095554c2 100644 --- a/test/Transforms/InstCombine/strncmp-1.ll +++ b/test/Transforms/InstCombine/strncmp-1.ll @@ -15,7 +15,7 @@ define i32 @test1(i8* %str2) { ; CHECK-LABEL: @test1( ; CHECK: %strcmpload = load i8* %str ; CHECK: %1 = zext i8 %strcmpload to i32 -; CHECK: %2 = sub i32 0, %1 +; CHECK: %2 = sub nsw i32 0, %1 ; CHECK: ret i32 %2 %str1 = getelementptr inbounds [1 x i8]* @null, i32 0, i32 0 @@ -73,7 +73,7 @@ define i32 @test6(i8* %str1, i8* %str2) { ; CHECK: [[ZEXT1:%[a-z]+]] = zext i8 [[LOAD1]] to i32 ; CHECK: [[LOAD2:%[a-z]+]] = load i8* %str2, align 1 ; CHECK: [[ZEXT2:%[a-z]+]] = zext i8 [[LOAD2]] to i32 -; CHECK: [[RET:%[a-z]+]] = sub i32 [[ZEXT1]], [[ZEXT2]] +; CHECK: [[RET:%[a-z]+]] = sub nsw i32 [[ZEXT1]], [[ZEXT2]] ; CHECK: ret i32 [[RET]] %temp1 = call i32 @strncmp(i8* %str1, i8* %str2, i32 1) diff --git a/test/Transforms/InstCombine/sub-xor.ll b/test/Transforms/InstCombine/sub-xor.ll index e7aff00ba8d..3a24074e72a 100644 --- a/test/Transforms/InstCombine/sub-xor.ll +++ b/test/Transforms/InstCombine/sub-xor.ll @@ -32,7 +32,7 @@ define i32 @test3(i32 %x) nounwind { ; CHECK-LABEL: @test3( ; CHECK-NEXT: and i32 %x, 31 -; CHECK-NEXT: sub i32 73, %and +; CHECK-NEXT: sub nsw i32 73, %and ; CHECK-NEXT: ret } diff --git a/test/Transforms/InstCombine/sub.ll b/test/Transforms/InstCombine/sub.ll index 114aff7efb8..0d310a8deeb 100644 --- a/test/Transforms/InstCombine/sub.ll +++ b/test/Transforms/InstCombine/sub.ll @@ -473,3 +473,39 @@ define i32 @test39(i32 %A, i32 %x) { ; CHECK: %C = add i32 %x, %A ; CHECK: ret i32 %C } + +define i16 @test40(i16 %a, i16 %b) { + %ashr = ashr i16 %a, 1 + %ashr1 = ashr i16 %b, 1 + %sub = sub i16 %ashr, %ashr1 + ret i16 %sub +; CHECK-LABEL: @test40( +; CHECK-NEXT: [[ASHR:%.*]] = ashr i16 %a, 1 +; CHECK-NEXT: [[ASHR1:%.*]] = ashr i16 %b, 1 +; CHECK-NEXT: [[RET:%.*]] = sub nsw i16 [[ASHR]], [[ASHR1]] +; CHECK: ret i16 [[RET]] +} + +define i32 @test41(i16 %a, i16 %b) { + %conv = sext i16 %a to i32 + %conv1 = sext i16 %b to i32 + %sub = sub i32 %conv, %conv1 + ret i32 %sub +; CHECK-LABEL: @test41( +; CHECK-NEXT: [[SEXT:%.*]] = sext i16 %a to i32 +; CHECK-NEXT: [[SEXT1:%.*]] = sext i16 %b to i32 +; CHECK-NEXT: [[RET:%.*]] = sub nsw i32 [[SEXT]], [[SEXT1]] +; CHECK: ret i32 [[RET]] +} + +define i4 @test42(i4 %x, i4 %y) { + %a = and i4 %y, 7 + %b = and i4 %x, 7 + %c = sub i4 %a, %b + ret i4 %c +; CHECK-LABEL: @test42( +; CHECK-NEXT: [[AND:%.*]] = and i4 %y, 7 +; CHECK-NEXT: [[AND1:%.*]] = and i4 %x, 7 +; CHECK-NEXT: [[RET:%.*]] = sub nsw i4 %a, %b +; CHECK: ret i4 [[RET]] +} -- 2.11.0