Index: lib/Transforms/InstCombine/InstCombine.h =================================================================== --- lib/Transforms/InstCombine/InstCombine.h +++ lib/Transforms/InstCombine/InstCombine.h @@ -247,6 +247,7 @@ bool DoXform = true); Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI); bool WillNotOverflowSignedAdd(Value *LHS, Value *RHS); + bool WillNotOverflowUnsignedAdd(Value *LHS, Value *RHS); Value *EmitGEPOffset(User *GEP); Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN); Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef Mask); Index: lib/Transforms/InstCombine/InstCombineAddSub.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -965,6 +965,23 @@ return false; } +/// WillNotOverflowUnsignedAdd - Return true if we can prove that: +/// (zext (add LHS, RHS)) === (add (zext LHS), (zext RHS)) +bool InstCombiner::WillNotOverflowUnsignedAdd(Value *LHS, Value *RHS) { + // There are different heuristics we can use for this. Here are some simple + // ones. + + // If the sign bit of LHS and that of RHS are both zero, no unsigned wrap. + bool LHSKnownNonNegative, LHSKnownNegative; + bool RHSKnownNonNegative, RHSKnownNegative; + ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, DL, 0); + ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, DL, 0); + if (LHSKnownNonNegative && RHSKnownNonNegative) + return true; + + return false; +} + Instruction *InstCombiner::visitAdd(BinaryOperator &I) { bool Changed = SimplifyAssociativeOrCommutative(I); Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); @@ -1244,6 +1261,10 @@ Changed = true; I.setHasNoSignedWrap(true); } + if (!I.hasNoUnsignedWrap() && WillNotOverflowUnsignedAdd(LHS, RHS)) { + Changed = true; + I.setHasNoUnsignedWrap(true); + } return Changed ? &I : nullptr; } Index: test/Transforms/InstCombine/AddOverFlow.ll =================================================================== --- test/Transforms/InstCombine/AddOverFlow.ll +++ test/Transforms/InstCombine/AddOverFlow.ll @@ -12,6 +12,28 @@ ret i16 %c } +define i16 @zero_sign_bit(i16 %a) { +; CHECK-LABEL: @zero_sign_bit( +; CHECK-NEXT: and +; CHECK-NEXT: add nuw +; CHECK-NEXT: ret + %1 = and i16 %a, 32767 + %2 = add i16 %1, 512 + ret i16 %2 +} + +define i16 @zero_sign_bit2(i16 %a, i16 %b) { +; CHECK-LABEL: @zero_sign_bit2( +; CHECK-NEXT: and +; CHECK-NEXT: and +; CHECK-NEXT: add nuw +; CHECK-NEXT: ret + %1 = and i16 %a, 32767 + %2 = and i16 %b, 32767 + %3 = add i16 %1, %2 + ret i16 %3 +} + ; CHECK-LABEL: @ripple_nsw1 ; CHECK: add nsw i16 %a, %b define i16 @ripple_nsw1(i16 %x, i16 %y) { @@ -45,7 +67,7 @@ } ; CHECK-LABEL: @ripple_no_nsw2 -; CHECK: add i16 %a, %b +; CHECK: add nuw i16 %a, %b define i16 @ripple_no_nsw2(i16 %x, i16 %y) { ; %a has at most one bit set %a = and i16 %y, 1 Index: test/Transforms/InstCombine/add-sitofp.ll =================================================================== --- test/Transforms/InstCombine/add-sitofp.ll +++ test/Transforms/InstCombine/add-sitofp.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -instcombine -S | grep "add nsw i32" +; RUN: opt < %s -instcombine -S | grep "add nuw nsw i32" define double @x(i32 %a, i32 %b) nounwind { %m = lshr i32 %a, 24 Index: test/Transforms/InstCombine/ffs-1.ll =================================================================== --- test/Transforms/InstCombine/ffs-1.ll +++ test/Transforms/InstCombine/ffs-1.ll @@ -103,7 +103,7 @@ ; CHECK-LABEL: @test_simplify13( %ret = call i32 @ffs(i32 %x) ; CHECK-NEXT: [[CTTZ:%[a-z0-9]+]] = call i32 @llvm.cttz.i32(i32 %x, i1 false) -; CHECK-NEXT: [[INC:%[a-z0-9]+]] = add nsw i32 [[CTTZ]], 1 +; CHECK-NEXT: [[INC:%[a-z0-9]+]] = add nuw nsw i32 [[CTTZ]], 1 ; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp ne i32 %x, 0 ; CHECK-NEXT: [[RET:%[a-z0-9]+]] = select i1 [[CMP]], i32 [[INC]], i32 0 ret i32 %ret @@ -114,7 +114,7 @@ ; CHECK-LINUX-LABEL: @test_simplify14( %ret = call i32 @ffsl(i32 %x) ; CHECK-LINUX-NEXT: [[CTTZ:%[a-z0-9]+]] = call i32 @llvm.cttz.i32(i32 %x, i1 false) -; CHECK-LINUX-NEXT: [[INC:%[a-z0-9]+]] = add nsw i32 [[CTTZ]], 1 +; CHECK-LINUX-NEXT: [[INC:%[a-z0-9]+]] = add nuw nsw i32 [[CTTZ]], 1 ; CHECK-LINUX-NEXT: [[CMP:%[a-z0-9]+]] = icmp ne i32 %x, 0 ; CHECK-LINUX-NEXT: [[RET:%[a-z0-9]+]] = select i1 [[CMP]], i32 [[INC]], i32 0 ret i32 %ret @@ -125,7 +125,7 @@ ; CHECK-LINUX-LABEL: @test_simplify15( %ret = call i32 @ffsll(i64 %x) ; CHECK-LINUX-NEXT: [[CTTZ:%[a-z0-9]+]] = call i64 @llvm.cttz.i64(i64 %x, i1 false) -; CHECK-LINUX-NEXT: [[INC:%[a-z0-9]+]] = add nsw i64 [[CTTZ]], 1 +; CHECK-LINUX-NEXT: [[INC:%[a-z0-9]+]] = add nuw nsw i64 [[CTTZ]], 1 ; CHECK-LINUX-NEXT: [[TRUNC:%[a-z0-9]+]] = trunc i64 [[INC]] to i32 ; CHECK-LINUX-NEXT: [[CMP:%[a-z0-9]+]] = icmp ne i64 %x, 0 ; CHECK-LINUX-NEXT: [[RET:%[a-z0-9]+]] = select i1 [[CMP]], i32 [[TRUNC]], i32 0 Index: test/Transforms/InstCombine/select.ll =================================================================== --- test/Transforms/InstCombine/select.ll +++ test/Transforms/InstCombine/select.ll @@ -281,7 +281,7 @@ ; CHECK-NEXT: %t1 = shl i32 %X, 8 ; CHECK-NEXT: %1 = and i32 %t1, 512 ; CHECK-NEXT: %2 = xor i32 %1, 512 -; CHECK-NEXT: %3 = add nsw i32 %2, 577 +; CHECK-NEXT: %3 = add nuw nsw i32 %2, 577 ; CHECK-NEXT: ret i32 %3 } @@ -294,7 +294,7 @@ ; CHECK-LABEL: @test15j( ; CHECK-NEXT: %t1 = shl i32 %X, 8 ; CHECK-NEXT: %1 = and i32 %t1, 512 -; CHECK-NEXT: %2 = add nsw i32 %1, 577 +; CHECK-NEXT: %2 = add nuw nsw i32 %1, 577 ; CHECK-NEXT: ret i32 %2 } @@ -521,7 +521,7 @@ ; CHECK-LABEL: @test35( ; CHECK: ashr i32 %x, 31 ; CHECK: and i32 {{.*}}, 40 -; CHECK: add nsw i32 {{.*}}, 60 +; CHECK: add nuw nsw i32 {{.*}}, 60 ; CHECK: ret } @@ -1235,4 +1235,4 @@ ; CHECK-NEXT: [[CMP:%[a-z0-9]+]] = icmp ult i32 %x, 68 ; CHECK-NEXT: [[SEL:%[a-z0-9]+]] = select i1 [[CMP]], i32 68, i32 %x ; CHECK-NEXT: ret i32 [[SEL]] -} \ No newline at end of file +}