[InstCombine] mark ADD with nuw if no unsigned overflow

[jingyue]

Summary

As a starting step, we only use one simple heuristic: if the sign bits
of both a and b are zero, we can prove "add a, b" do not unsigned
overflow, and thus convert it to "add nuw a, b".

Updated all affected tests and added two new tests (@zero_sign_bit and
@zero_sign_bit2) in AddOverflow.ll

[chandlerc]

Minor comment, LGTM with the obvious adjustment.

I worry a little about how many times we compute the known sign bits here, but that's nothing new in this patch.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1265

This should be an else if, no? If we succeed at adding NSW, why would we check for NUW?

[jingyue]

Thanks for your review! I agree with your concerns. computeKnownBits is a little expensive. I'm considering merging WillNotOverflowSignedAdd and WillNotOverflowUnsignedAdd in a separate patch.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1265

Even with nsw, there's still value of checking for NUW. e.g., "add i16 16383, 16383" can be marked with both nsw and nuw, while "add i16 65535, 65535" can be marked with only nsw but not nuw.

[chandlerc]

Cool.

[meheff]

LGTM

lib/Transforms/InstCombine/InstCombineAddSub.cpp

972

nit: The comment suggests more than one technique for ruling out unsigned overflow, but only one is actually used.

[jingyue]

Fixed some comments. Thanks Chandler and Mark!

lib/Transforms/InstCombine/InstCombine.h

private:
   Instruction *tryOptimizeCall(CallInst *CI, const DataLayout *DL);
   bool transformConstExprCastCall(CallSite CS);
   Instruction *transformCallThroughTrampoline(CallSite CS,
                                               IntrinsicInst *Tramp);
   Instruction *transformZExtICmp(ICmpInst *ICI, Instruction &CI,
                                  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<int> Mask);
 
 public:
   // InsertNewInstBefore - insert an instruction New before instruction Old
   // in the program.  Add the new instruction to the worklist.
   //

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (IntegerType *IT = dyn_cast<IntegerType>(LHS->getType())) {
     if (checkRippleForAdd(LHSKnownZero, RHSKnownZero))
       return true;
     if (checkRippleForAdd(RHSKnownZero, LHSKnownZero))
       return true;
   }
   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 is a simple one.
+  // 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);
 
   if (Value *V = SimplifyVectorOp(I))
     return ReplaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(),
if (match(RHS, m_Xor(m_Value(A), m_Value(B))) &&
       return BinaryOperator::CreateOr(A, B);
 
     if (match(LHS, m_Xor(m_Value(A), m_Value(B))) &&
         (match(RHS, m_And(m_Specific(A), m_Specific(B))) ||
          match(RHS, m_And(m_Specific(B), m_Specific(A)))))
       return BinaryOperator::CreateOr(A, B);
   }
 
+  // TODO(jingyue): Consider WillNotOverflowSignedAdd and
+  // WillNotOverflowUnsignedAdd to reduce the number of invocations of
+  // computeKnownBits.
   if (!I.hasNoSignedWrap() && WillNotOverflowSignedAdd(LHS, RHS)) {
     Changed = true;
     I.setHasNoSignedWrap(true);
   }
+  if (!I.hasNoUnsignedWrap() && WillNotOverflowUnsignedAdd(LHS, RHS)) {
+    Changed = true;
+    I.setHasNoUnsignedWrap(true);
+  }
 
   return Changed ? &I : nullptr;
 }
 
 Instruction *InstCombiner::visitFAdd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 

test/Transforms/InstCombine/AddOverFlow.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; CHECK-LABEL: @oppositesign
 ; CHECK: add nsw i16 %a, %b
 define i16 @oppositesign(i16 %x, i16 %y) {
 ; %a is negative, %b is positive
   %a = or i16 %x, 32768
   %b = and i16 %y, 32767
   %c = add i16 %a, %b
   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) {
 ; %a has at most one bit set
   %a = and i16 %y, 1
 
 ; %b has a 0 bit other than the sign bit
   %b = and i16 %x, 49151

 define i32 @ripple_no_nsw1(i32 %x, i32 %y) {
 ; We know nothing about %x
   %a = and i32 %y, 1
   %b = add i32 %a, %x
   ret i32 %b
 }
 
 ; 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
 
 ; %b has a 0 bit, but it is the sign bit
   %b = and i16 %x, 32767
 
   %c = add i16 %a, %b
   ret i16 %c
 }

test/Transforms/InstCombine/add-sitofp.ll

-; 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
   %n = and i32 %m, %b
   %o = sitofp i32 %n to double
   %p = fadd double %o, 1.0
   ret double %p
 }

test/Transforms/InstCombine/ffs-1.ll

 }
 
 ; Check ffs(x) -> x != 0 ? (i32)llvm.cttz(x) + 1 : 0.
 
 define i32 @test_simplify13(i32 %x) {
 ; 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
 ; CHECK-NEXT: ret i32 [[RET]]
 }
 
 define i32 @test_simplify14(i32 %x) {
 ; 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
 ; CHECK-LINUX-NEXT: ret i32 [[RET]]
 }
 
 define i32 @test_simplify15(i64 %x) {
 ; 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
   ret i32 %ret
 ; CHECK-LINUX-NEXT: ret i32 [[RET]]
 }

test/Transforms/InstCombine/select.ll

define i32 @test15i(i32 %X) {
         %t1 = and i32 %X, 2
         %t2 = icmp ne i32 %t1, 0
         %t3 = select i1 %t2, i32 577, i32 1089
         ret i32 %t3
 ; CHECK-LABEL: @test15i(
 ; 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
 }
 
 ;; (a & 2) ? 1089 : 577
 define i32 @test15j(i32 %X) {
         %t1 = and i32 %X, 2
         %t2 = icmp ne i32 %t1, 0
         %t3 = select i1 %t2, i32 1089, i32 577
         ret i32 %t3
 ; 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
 }
 
 define i32 @test16(i1 %C, i32* %P) {
         %P2 = select i1 %C, i32* %P, i32* null          
         %V = load i32* %P2              
         ret i32 %V
 ; CHECK-LABEL: @test16(

 
 define i32 @test35(i32 %x) {
   %cmp = icmp sge i32 %x, 0
   %cond = select i1 %cmp, i32 60, i32 100
   ret i32 %cond
 ; 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
 }
 
 define i32 @test36(i32 %x) {
   %cmp = icmp slt i32 %x, 0
   %cond = select i1 %cmp, i32 60, i32 100
   ret i32 %cond
 ; CHECK-LABEL: @test36(
define i32 @test75(i32 %x) {
   %cond = select i1 %cmp, i32 47, i32 %x
   %cmp3 = icmp ult i32 %cond, 68
   %retval = select i1 %cmp3, i32 68, i32 %cond
   ret i32 %retval
 ; CHECK-LABEL: @test75(
 ; 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]]
-}
+}