[InstCombine] sub X, sext(bool Y) -> add X, zext(bool Y)

[spatel]

Summary

I noticed the base case in D24527, and that is hopefully simple enough. Please let me know if I've thought about the nsw/nuw cases correctly.

[spatel]

Ping.

Minor update:
Not sure if the use of 'auto' was welcome here, so I changed it to 'BinaryOperator *Add'.

[efriedma]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1648 ↗

(On Diff #73964)

I would favor dropping the nuw flag over keeping IR in a form that isn't canonical.

test/Transforms/InstCombine/urem.ll

32 ↗

(On Diff #73964)

For example, this seems better than "sub nuw i5 %x, %tmp".

[spatel]

Patch updated as suggested by Eli:
Favor the simpler zext+add sequence over keeping an 'nuw' flag.

[efriedma]

Please make sure we have a test to check that we can correctly reverse the transform in SelectionDAG when we need to (for example, make sure we don't genereate an unnecessary AND for a vector compare on x86).

Otherwise LGTM.

[spatel]

In D25135#569638, @efriedma wrote:

Please make sure we have a test to check that we can correctly reverse the transform in SelectionDAG when we need to (for example, make sure we don't genereate an unnecessary AND for a vector compare on x86).

How did you see that one coming? :)
Indeed, x86 doesn't deal with this and gets worse. This might be the same as the fixes needed before D25485 can proceed...

define <4 x i32> @foo(<4 x i32> %x, <4 x i32> %y, <4 x i32> %z) {
  %cmp = icmp eq <4 x i32> %x, %y
  %sext = sext <4 x i1> %cmp to <4 x i32>
  %sub = sub <4 x i32> %z, %sext
  ret <4 x i32> %sub
}

We have this:

vpcmpeqd	%xmm1, %xmm0, %xmm0
vpsubd	%xmm0, %xmm2, %xmm0

But with this patch, we get this:

vpcmpeqd	%xmm1, %xmm0, %xmm0
vpsrld	$31, %xmm0, %xmm0
vpaddd	%xmm2, %xmm0, %xmm0

[spatel]

Oh wow, I hadn't updated in a day. @RKSimon just fixed this with D25374 / rL284015. The last test case in that patch is nearly what I posted here. :)

llvm/trunk/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && match(Op0, m_Zero()) &&
         C->isNotMinSignedValue() && !C->isOneValue())
       return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C));
 
     // 0 - (X << Y)  -> (-X << Y)   when X is freely negatable.
     if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
       if (Value *XNeg = dyn_castNegVal(X))
         return BinaryOperator::CreateShl(XNeg, Y);
 
+    // Subtracting -1/0 is the same as adding 1/0:
+    // sub [nsw] Op0, sext(bool Y) -> add [nsw] Op0, zext(bool Y)
+    // 'nuw' is dropped in favor of the canonical form.
+    if (match(Op1, m_SExt(m_Value(Y))) &&
+        Y->getType()->getScalarSizeInBits() == 1) {
+      Value *Zext = Builder->CreateZExt(Y, I.getType());
+      BinaryOperator *Add = BinaryOperator::CreateAdd(Op0, Zext);
+      Add->setHasNoSignedWrap(I.hasNoSignedWrap());
+      return Add;
+    }
+
     // X - A*-B -> X + A*B
     // X - -A*B -> X + A*B
     Value *A, *B;
     if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) ||
         match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B))))
       return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B));
 
     // X - A*CI -> X + A*-CI

llvm/trunk/test/Transforms/InstCombine/sub.ll

 ; CHECK-NEXT:    [[SUB:%.*]] = select i1 %A, i32 0, i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ;
   %sel0 = select i1 %A, i32 %B, i32 %D
   %sel1 = select i1 %A, i32 %B, i32 %C
   %sub = sub i32 %sel0, %sel1
   ret i32 %sub
 }
+
+; Zext+add is more canonical than sext+sub.
+
+define i8 @bool_sext_sub(i8 %x, i1 %y) {
+; CHECK-LABEL: @bool_sext_sub(
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i1 %y to i8
+; CHECK-NEXT:    [[SUB:%.*]] = add i8 [[TMP1]], %x
+; CHECK-NEXT:    ret i8 [[SUB]]
+;
+  %sext = sext i1 %y to i8
+  %sub = sub i8 %x, %sext
+  ret i8 %sub
+}
+
+; Vectors get the same transform.
+
+define <2 x i8> @bool_sext_sub_vec(<2 x i8> %x, <2 x i1> %y) {
+; CHECK-LABEL: @bool_sext_sub_vec(
+; CHECK-NEXT:    [[TMP1:%.*]] = zext <2 x i1> %y to <2 x i8>
+; CHECK-NEXT:    [[SUB:%.*]] = add <2 x i8> [[TMP1]], %x
+; CHECK-NEXT:    ret <2 x i8> [[SUB]]
+;
+  %sext = sext <2 x i1> %y to <2 x i8>
+  %sub = sub <2 x i8> %x, %sext
+  ret <2 x i8> %sub
+}
+
+; NSW is preserved.
+
+define <2 x i8> @bool_sext_sub_vec_nsw(<2 x i8> %x, <2 x i1> %y) {
+; CHECK-LABEL: @bool_sext_sub_vec_nsw(
+; CHECK-NEXT:    [[TMP1:%.*]] = zext <2 x i1> %y to <2 x i8>
+; CHECK-NEXT:    [[SUB:%.*]] = add nsw <2 x i8> [[TMP1]], %x
+; CHECK-NEXT:    ret <2 x i8> [[SUB]]
+;
+  %sext = sext <2 x i1> %y to <2 x i8>
+  %sub = sub nsw <2 x i8> %x, %sext
+  ret <2 x i8> %sub
+}
+
+; We favor the canonical zext+add over keeping the NUW.
+
+define i8 @bool_sext_sub_nuw(i8 %x, i1 %y) {
+; CHECK-LABEL: @bool_sext_sub_nuw(
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i1 %y to i8
+; CHECK-NEXT:    [[SUB:%.*]] = add i8 [[TMP1]], %x
+; CHECK-NEXT:    ret i8 [[SUB]]
+;
+  %sext = sext i1 %y to i8
+  %sub = sub nuw i8 %x, %sext
+  ret i8 %sub
+}
+

llvm/trunk/test/Transforms/InstCombine/urem.ll

 ; CHECK-NEXT:    [[TMP2:%.*]] = add i8 %x, 127
 ; CHECK-NEXT:    [[REM:%.*]] = select i1 [[TMP1]], i8 %x, i8 [[TMP2]]
 ; CHECK-NEXT:    ret i8 [[REM]]
 ;
   %rem = urem i8 %x, 129
   ret i8 %rem
 }
 
-; TODO: Should this be zext+add instead of sext+sub?
 define i5 @biggest_divisor(i5 %x) {
 ; CHECK-LABEL: @biggest_divisor(
 ; CHECK-NEXT:    [[NOT_:%.*]] = icmp eq i5 %x, -1
-; CHECK-NEXT:    [[TMP1:%.*]] = sext i1 [[NOT_]] to i5
-; CHECK-NEXT:    [[REM:%.*]] = sub i5 %x, [[TMP1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i1 [[NOT_]] to i5
+; CHECK-NEXT:    [[REM:%.*]] = add i5 [[TMP1]], %x
 ; CHECK-NEXT:    ret i5 [[REM]]
 ;
   %rem = urem i5 %x, -1
   ret i5 %rem
 }
 
 ; TODO: Should vector subtract of constant be canonicalized to add?
 define <2 x i4> @big_divisor_vec(<2 x i4> %x) {