[InstCombine] reduce demand-limited bool math to logic

[spatel]

Summary

The cmp math test is inspired by memcmp() patterns seen in D75840. I know there's at least 1 related fold we can do here if both values are sext'd, but I'm not seeing a way to generalize further.

I know we have some other bool math patterns that we want to reduce, but that might require fixing the bogus transforms noted in D72396.

Alive proof translations of the regression tests:
https://rise4fun.com/Alive/zGWi

Name: demand add 1
  %xz = zext i1 %x to i32
  %ys = sext i1 %y to i32
  %sub = add i32 %xz, %ys
  %r = lshr i32 %sub, 31
=>
  %notx = xor i1 %x, 1
  %and = and i1 %y, %notx
  %r = zext i1 %and to i32
  
Name: demand add 2
  %xz = zext i1 %x to i5
  %ys = sext i1 %y to i5
  %sub = add i5 %xz, %ys
  %r = and i5 %sub, 16
  =>
  %notx = xor i1 %x, 1
  %and = and i1 %y, %notx
  %r = select i1 %and, i5 -16, i5 0

Name: demand add 3
  %xz = zext i1 %x to i8
  %ys = sext i1 %y to i8
  %a = add i8 %ys, %xz
  %r = ashr i8 %a, 7
=>
  %notx = xor i1 %x, 1
  %and = and i1 %y, %notx
  %r = sext i1 %and to i8
  
Name: cmp math
  %gt = icmp ugt i32 %x, %y
  %lt = icmp ult i32 %x, %y
  %xz = zext i1 %gt to i32
  %yz = zext i1 %lt to i32
  %s = sub i32 %xz, %yz
  %r = lshr i32 %s, 31
=>
  %r = zext i1 %lt to i32

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

457

Wouldn't it be sufficient to check that the LSB is not demanded? I don't think we care that specifically the MSB is demanded, any of the top bits could be.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

457

Yes - good point. Once the low-bit is removed, the result can only be 0 or -1.

[spatel]

Patch updated:

1. Change the demanded mask predicate to be more liberal; we only need to know that the low-bit is not demanded.
2. Update tests to more accurately check the mask constraint (adjust 'and' mask and shift amounts).

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

case Instruction::SExt: {
 
     // If the sign bit of the input is known set or clear, then we know the
     // top bits of the result.
     Known = InputKnown.sext(BitWidth);
     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
     break;
   }
   case Instruction::Add:
+    if ((DemandedMask & 1) == 0) {
+      // If we do not need the low bit, try to convert bool math to logic:
+      //   add iN (zext i1 X), (sext i1 Y) --> sext (~X & Y) to iN
+      // Truth table for inputs and output signbits:
+      //       X:0 | X:1
+      //      ----------
+      // Y:0  |  0 | 0 |
+      // Y:1  | -1 | 0 |
+      //      ----------
+      Value *X, *Y;
+      if (match(I, m_c_Add(m_OneUse(m_ZExt(m_Value(X))),
+                           m_OneUse(m_SExt(m_Value(Y))))) &&
+          X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType()) {
+        IRBuilderBase::InsertPointGuard Guard(Builder);
+        Builder.SetInsertPoint(I);
+        Value *AndNot = Builder.CreateAnd(Builder.CreateNot(X), Y);
+        return Builder.CreateSExt(AndNot, VTy);
+      }
+    }
+    LLVM_FALLTHROUGH;
   case Instruction::Sub: {
     /// If the high-bits of an ADD/SUB are not demanded, then we do not care
     /// about the high bits of the operands.
     unsigned NLZ = DemandedMask.countLeadingZeros();
     // Right fill the mask of bits for this ADD/SUB to demand the most
     // significant bit and all those below it.
     APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ));
     if (ShrinkDemandedConstant(I, 0, DemandedFromOps) ||

llvm/test/Transforms/InstCombine/add.ll

 ;
   %B = or <2 x i32> %A, <i32 123, i32 456>
   %C = add <2 x i32> %B, <i32 -123, i32 -456>
   ret <2 x i32> %C
 }
 
 define i32 @lshr_add(i1 %x, i1 %y) {
 ; CHECK-LABEL: @lshr_add(
-; CHECK-NEXT:    [[XZ:%.*]] = zext i1 [[X:%.*]] to i32
-; CHECK-NEXT:    [[YS:%.*]] = sext i1 [[Y:%.*]] to i32
-; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[XZ]], [[YS]]
-; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[SUB]], 31
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = zext i1 [[TMP2]] to i32
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %xz = zext i1 %x to i32
   %ys = sext i1 %y to i32
   %sub = add i32 %xz, %ys
   %r = lshr i32 %sub, 31
   ret i32 %r
 }
 
 define i5 @and_add(i1 %x, i1 %y) {
 ; CHECK-LABEL: @and_add(
-; CHECK-NEXT:    [[XZ:%.*]] = zext i1 [[X:%.*]] to i5
-; CHECK-NEXT:    [[YS:%.*]] = sext i1 [[Y:%.*]] to i5
-; CHECK-NEXT:    [[SUB:%.*]] = add nsw i5 [[XZ]], [[YS]]
-; CHECK-NEXT:    [[R:%.*]] = and i5 [[SUB]], -2
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP2]], i5 -2, i5 0
 ; CHECK-NEXT:    ret i5 [[R]]
 ;
   %xz = zext i1 %x to i5
   %ys = sext i1 %y to i5
   %sub = add i5 %xz, %ys
   %r = and i5 %sub, 30
   ret i5 %r
 }
 
 define <2 x i8> @ashr_add_commute(<2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @ashr_add_commute(
-; CHECK-NEXT:    [[XZ:%.*]] = zext <2 x i1> [[X:%.*]] to <2 x i8>
-; CHECK-NEXT:    [[YS:%.*]] = sext <2 x i1> [[Y:%.*]] to <2 x i8>
-; CHECK-NEXT:    [[SUB:%.*]] = add nsw <2 x i8> [[YS]], [[XZ]]
-; CHECK-NEXT:    [[R:%.*]] = ashr <2 x i8> [[SUB]], <i8 1, i8 1>
-; CHECK-NEXT:    ret <2 x i8> [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i1> [[X:%.*]], <i1 true, i1 true>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i1> [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sext <2 x i1> [[TMP2]] to <2 x i8>
+; CHECK-NEXT:    ret <2 x i8> [[TMP3]]
 ;
   %xz = zext <2 x i1> %x to <2 x i8>
   %ys = sext <2 x i1> %y to <2 x i8>
   %sub = add nsw <2 x i8> %ys, %xz
   %r = ashr <2 x i8> %sub, <i8 1, i8 1>
   ret <2 x i8> %r
 }
 
 define i32 @cmp_math(i32 %x, i32 %y) {
 ; CHECK-LABEL: @cmp_math(
-; CHECK-NEXT:    [[GT:%.*]] = icmp ugt i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[LT:%.*]] = icmp ult i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[XZ:%.*]] = zext i1 [[GT]] to i32
-; CHECK-NEXT:    [[TMP1:%.*]] = sext i1 [[LT]] to i32
-; CHECK-NEXT:    [[S:%.*]] = add nsw i32 [[XZ]], [[TMP1]]
-; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[S]], 31
+; CHECK-NEXT:    [[LT:%.*]] = icmp ult i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = zext i1 [[LT]] to i32
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %gt = icmp ugt i32 %x, %y
   %lt = icmp ult i32 %x, %y
   %xz = zext i1 %gt to i32
   %yz = zext i1 %lt to i32
   %s = sub i32 %xz, %yz
   %r = lshr i32 %s, 31
   ret i32 %r
 }
 
+; Negative test - wrong type
+
 define i32 @lshr_add_nonbool(i2 %x, i1 %y) {
 ; CHECK-LABEL: @lshr_add_nonbool(
 ; CHECK-NEXT:    [[XZ:%.*]] = zext i2 [[X:%.*]] to i32
 ; CHECK-NEXT:    [[YS:%.*]] = sext i1 [[Y:%.*]] to i32
 ; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[XZ]], [[YS]]
 ; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[SUB]], 31
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %xz = zext i2 %x to i32
   %ys = sext i1 %y to i32
   %sub = add i32 %xz, %ys
   %r = lshr i32 %sub, 31
   ret i32 %r
 }
 
+; Negative test - wrong demand
+
 define i32 @and31_add(i1 %x, i1 %y) {
 ; CHECK-LABEL: @and31_add(
 ; CHECK-NEXT:    [[XZ:%.*]] = zext i1 [[X:%.*]] to i32
 ; CHECK-NEXT:    [[YS:%.*]] = sext i1 [[Y:%.*]] to i32
 ; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[XZ]], [[YS]]
 ; CHECK-NEXT:    [[R:%.*]] = and i32 [[SUB]], 31
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %xz = zext i1 %x to i32
   %ys = sext i1 %y to i32
   %sub = add i32 %xz, %ys
   %r = and i32 %sub, 31
   ret i32 %r
 }
 
+; Negative test - extra use
+
 define i32 @lshr_add_use(i1 %x, i1 %y, i32* %p) {
 ; CHECK-LABEL: @lshr_add_use(
 ; CHECK-NEXT:    [[XZ:%.*]] = zext i1 [[X:%.*]] to i32
 ; CHECK-NEXT:    store i32 [[XZ]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[YS:%.*]] = sext i1 [[Y:%.*]] to i32
 ; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[XZ]], [[YS]]
 ; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[SUB]], 31
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %xz = zext i1 %x to i32
   store i32 %xz, i32* %p
   %ys = sext i1 %y to i32
   %sub = add i32 %xz, %ys
   %r = lshr i32 %sub, 31
   ret i32 %r
 }
 
+; Negative test - extra use
+
 define i32 @lshr_add_use2(i1 %x, i1 %y, i32* %p) {
 ; CHECK-LABEL: @lshr_add_use2(
 ; CHECK-NEXT:    [[XZ:%.*]] = zext i1 [[X:%.*]] to i32
 ; CHECK-NEXT:    [[YS:%.*]] = sext i1 [[Y:%.*]] to i32
 ; CHECK-NEXT:    store i32 [[YS]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[XZ]], [[YS]]
 ; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[SUB]], 31
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %xz = zext i1 %x to i32
   %ys = sext i1 %y to i32
   store i32 %ys, i32* %p
   %sub = add i32 %xz, %ys
   %r = lshr i32 %sub, 31
   ret i32 %r
 }