[InstCombine] Transform (A > 0) | (A < 0) -> zext (A != 0) fold

[XChy]

Summary

[InstCombine] Transform (A > 0) | (A < 0) -> zext (A != 0) fold

This extends foldCastedBitwiseLogic to handle the similar cases.

Actually, for (A > B) | (A < B), when B != 0, it can be optimized to zext( A != B ) by foldAndOrOfICmpsUsingRanges.
However, when B = 0, transformZExtICmp will transform zext(A < 0) to i32 into A >> 31,
which cannot be optimized by foldAndOrOfICmpsUsingRanges.

Because I'm new to LLVM and has no concise knowledge about how LLVM decides the order of optimization,
I choose to extend foldCastedBitwiseLogic to fold ( A >> (X - 1) ) | ((A > 0) zext to iX) -> (A != 0) zext to iX.

And the equivalent fold follows:

A >> (X - 1) ) | ((A > 0) zext to iX
 -> A < 0 | A > 0
 -> (A != 0) zext to iX

It's proved by alive-tv

Related issue:
(a > b) | (a < b) is not simplified only for the case b=0

[goldstein.w.n]

Thank you for the patch and welcome!

We actually seem to handle this as long as its (zext (or slt, sgt)): https://alive2.llvm.org/ce/z/Fpyw7G
Its only if we have (or (zext slt), (zext sgt)) that we fail.

I think the best approach we actually be to fold:(bitwise_logic (zext A), (zext B)) -> (zext (bitwise_logic A, B)). That will cover this case any may help other cases.

Edit: Ah I see, we already do that (https://alive2.llvm.org/ce/z/nXUetC), we just mess up the pattern here.

[goldstein.w.n]

In D154126#4461039, @goldstein.w.n wrote:

Thank you for the patch and welcome!

We actually seem to handle this as long as its (zext (or slt, sgt)): https://alive2.llvm.org/ce/z/Fpyw7G
Its only if we have (or (zext slt), (zext sgt)) that we fail.

I think the best approach we actually be to fold:(bitwise_logic (zext A), (zext B)) -> (zext (bitwise_logic A, B)). That will cover this case any may help other cases.

Edit: Ah I see, we already do that (https://alive2.llvm.org/ce/z/nXUetC), we just mess up the pattern here.

It might also be easier to just update the fold for (or slt, sgt) to look through zext.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1720

Style pred -> Pred.

1722

m_ConstantInt(B) -> m_APInt(B) (and make B a const APInt *).

1723

m_SpecificInt(0) -> m_Zero().

1725

Instead of duplicating the matching logic for both orders, can you create a lambda that tries the match on maybe Lhs and Rhs then just call it with (Op0, Op1) and (Op1, Op0).
Another approach is to match match(&I, m_c_ICmp(<your logic for one of the cases here>)). (note the m_c prefix means commutative i.e try swapping the arg positions).

1726

A->getType()->getScalarBitWidth

1728

A->getType()->isIntegerTy() is unneeded, this is ICmp (IntegerCmp)... I think.

1729

Style cmp variable should be Cmp.

1731

Builder.getInt(APInt::getZero(A->getType()->getIntegerBitWidth())) -> Constant::getNullValue(A->getType())

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2595

Can you add:

1. A vector test.
2. A few negative tests (maybe ashr instead of lshr, slt instead of sgt, incorrect shift amt).

[XChy]

Thanks for your review and advice!
I have updated my patch and added support for vector.
I would appreciate it if you could review it and offer some advice.

[XChy]

[Format the code to pass the patch test]

[XChy]

This comment was removed by XChy.

[XChy]

[Rebase commits to pass the patch test]

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1724

Since you only use the constant as a splat just match B as an m_APInt(B). And make B a const APInt *.

1737

The Pred == ICmpInst::ICMP_SGT should probably be at the top when you check that logicop is Or.

[goldstein.w.n]

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2684

Can you split the tests to a seperate patch?

Basically
Commit 1: Tests
Commit 2: Impl (Update tests so we can see the changes the impl causes)

Then you set the relationship between the patches using the "Edit Related Revisions" Options on Phabricator.

[XChy]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1724

Good advice, you remind me of m_APInt can match splated vector.

1737

Thanks for advice, but maybe Pred's value is decided by MatchOrZextIcmp function, so Pred == xxx must be after MatchOrZextIcmp.

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2684

OK, thanks for instruction, I will get them done next morning.

[goldstein.w.n]

Other than a few nits, looks basically good.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1723

nit: ZextIcmp -> ZExtICmp.

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2648

nit, can you replace <test>_neg<N> -> <test>_fail<N> (neg can also be 0-X).

2675–2692

you already test incorrect shift amount, maybe keep this one with correct shift amount but change the icmp to sgt X, 1 (or any non-zero).

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1733

You can include this check directly in the match above using m_SpecificInt(X - 1).

[XChy]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1733

The type of A is determined during the match, but X = A->getType()->getScalarSizeInBits() must be passed to the m_SpecificInt before matching. Actually, X keep zero before the match.

Or do you mean something like:

auto MatchOrZExtICmp = [&](Value *Op0, Value *Op1) -> bool {
    const Value *X;
    return match(Op0, m_LShr(m_Value(A), m_Value(X))) &&
           match(X, m_SpecificInt(A->getType()->getScalarSizeInBits() - 1)) &&
           match(Op1, m_ZExt(m_ICmp(Pred, m_Specific(A), m_Zero())));
  };

I'm not sure how to solve this problem. Could you help me with it?

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1733

A has the same type as Op0 and Op1

[goldstein.w.n]

LGTM.

Do you have commit access?
If not can you give me your email/name so I can commit for you.

[XChy]

In D154126#4467170, @goldstein.w.n wrote:

LGTM.

Do you have commit access?
If not can you give me your email/name so I can commit for you.

No, I have not commit access.
I would appreciate it if you could commit it.
My email is [e-mail].
My name is XChy.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

 }
 
 /// Fold {and,or,xor} (cast X), Y.
 Instruction *InstCombinerImpl::foldCastedBitwiseLogic(BinaryOperator &I) {
   auto LogicOpc = I.getOpcode();
   assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic folding");
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
+
+  // ( A << (X - 1) ) | ((A > 0) zext to iX)
+  // <=> A < 0 | A > 0
+  // <=> (A != 0) zext to iX
+  Value *A;
+  Constant *B;
+  ICmpInst::Predicate Pred;
+
+  auto MatchOrZextIcmp = [&](Value *Op0, Value *Op1) -> bool {
+    return match(Op0, m_LShr(m_Value(A), m_Constant(B))) &&
+           match(Op1, m_ZExt(m_ICmp(Pred, m_Specific(A), m_Zero())));
+  };
+
+  if (LogicOpc == Instruction::Or &&
+      (MatchOrZextIcmp(Op0, Op1) || MatchOrZextIcmp(Op1, Op0))) {
+    uint64_t X = A->getType()->getScalarSizeInBits();
+    bool MatchBAndX;
+    if (B->getType()->isIntegerTy())
+      MatchBAndX = cast<ConstantInt>(B)->equalsInt(X - 1);
+    else
+      MatchBAndX = cast<ConstantInt>(B->getSplatValue())->equalsInt(X - 1);
+
+    if (Pred == ICmpInst::ICMP_SGT && MatchBAndX) {
+      Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_NE, A,
+                                      Constant::getNullValue(A->getType()));
+      return new ZExtInst(Cmp, A->getType());
+    }
+  }
+
   CastInst *Cast0 = dyn_cast<CastInst>(Op0);
   if (!Cast0)
     return nullptr;
 
   // This must be a cast from an integer or integer vector source type to allow
   // transformation of the logic operation to the source type.
   Type *DestTy = I.getType();
   Type *SrcTy = Cast0->getSrcTy();

llvm/test/Transforms/InstCombine/and-or-icmps.ll

 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %rx = icmp ne <2 x i8> %x, <i8 -1, i8 -1>
   %ry = icmp ne <2 x i8> %y, <i8 -1, i8 undef>
   %r = or <2 x i1> %rx, %ry
   ret <2 x i1> %r
 }
 
+
 define i32 @icmp_slt_0_or_icmp_sgt_0_i32(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i32(
-; CHECK-NEXT:    [[B:%.*]] = icmp sgt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[X_LOBIT:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = zext i1 [[B]] to i32
-; CHECK-NEXT:    [[E:%.*]] = or i32 [[X_LOBIT]], [[D]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[E:%.*]] = zext i1 [[TMP1]] to i32
 ; CHECK-NEXT:    ret i32 [[E]]
 ;
   %A = icmp slt i32 %x, 0
   %B = icmp sgt i32 %x, 0
   %C = zext i1 %A to i32
   %D = zext i1 %B to i32
   %E = or i32 %C, %D
   ret i32 %E
 }
 
+
 define i64 @icmp_slt_0_or_icmp_sgt_0_i64(i64 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i64(
-; CHECK-NEXT:    [[B:%.*]] = icmp sgt i64 [[X:%.*]], 0
-; CHECK-NEXT:    [[X_LOBIT:%.*]] = lshr i64 [[X]], 63
-; CHECK-NEXT:    [[D:%.*]] = zext i1 [[B]] to i64
-; CHECK-NEXT:    [[E:%.*]] = or i64 [[X_LOBIT]], [[D]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i64 [[X:%.*]], 0
+; CHECK-NEXT:    [[E:%.*]] = zext i1 [[TMP1]] to i64
 ; CHECK-NEXT:    ret i64 [[E]]
 ;
   %A = icmp slt i64 %x, 0
   %B = icmp sgt i64 %x, 0
   %C = zext i1 %A to i64
   %D = zext i1 %B to i64
   %E = or i64 %C, %D
   ret i64 %E
 }
 
+
 define i64 @icmp_slt_0_or_icmp_sgt_0_i64_neg0(i64 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i64_neg0(
 ; CHECK-NEXT:    [[E:%.*]] = lshr i64 [[X:%.*]], 63
 ; CHECK-NEXT:    ret i64 [[E]]
 ;
   %B = icmp slt i64 %x, 0
   %C = lshr i64 %x, 63
   %D = zext i1 %B to i64
   %E = or i64 %C, %D
   ret i64 %E
 }
 
+
 define i64 @icmp_slt_0_or_icmp_sgt_0_i64_neg1(i64 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i64_neg1(
 ; CHECK-NEXT:    [[B:%.*]] = icmp sgt i64 [[X:%.*]], 0
 ; CHECK-NEXT:    [[C:%.*]] = ashr i64 [[X]], 63
 ; CHECK-NEXT:    [[D:%.*]] = zext i1 [[B]] to i64
 ; CHECK-NEXT:    [[E:%.*]] = or i64 [[C]], [[D]]
 ; CHECK-NEXT:    ret i64 [[E]]
 ;
   %B = icmp sgt i64 %x, 0
   %C = ashr i64 %x, 63
   %D = zext i1 %B to i64
   %E = or i64 %C, %D
   ret i64 %E
 }
 
+
 define i64 @icmp_slt_0_or_icmp_sgt_0_i64_neg2(i64 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i64_neg2(
 ; CHECK-NEXT:    [[B:%.*]] = icmp sgt i64 [[X:%.*]], 0
 ; CHECK-NEXT:    [[C:%.*]] = ashr i64 [[X]], 62
 ; CHECK-NEXT:    [[D:%.*]] = zext i1 [[B]] to i64
 ; CHECK-NEXT:    [[E:%.*]] = or i64 [[C]], [[D]]
 ; CHECK-NEXT:    ret i64 [[E]]
 ;
   %B = icmp sgt i64 %x, 0
   %C = ashr i64 %x, 62
   %D = zext i1 %B to i64
   %E = or i64 %C, %D
   ret i64 %E
 }
 
+
 define i64 @icmp_slt_0_or_icmp_sgt_0_i64_neg3(i64 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i64_neg3(
 ; CHECK-NEXT:    [[C:%.*]] = ashr i64 [[X:%.*]], 62
 ; CHECK-NEXT:    [[X_LOBIT:%.*]] = lshr i64 [[X]], 63
 ; CHECK-NEXT:    [[E:%.*]] = or i64 [[C]], [[X_LOBIT]]
 ; CHECK-NEXT:    ret i64 [[E]]
 ;
   %B = icmp slt i64 %x, 0
   %C = ashr i64 %x, 62
   %D = zext i1 %B to i64
   %E = or i64 %C, %D
   ret i64 %E
 }
 
+
 define <2 x i64> @icmp_slt_0_or_icmp_sgt_0_i64x2(<2 x i64> %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i64x2(
-; CHECK-NEXT:    [[B:%.*]] = icmp sgt <2 x i64> [[X:%.*]], zeroinitializer
-; CHECK-NEXT:    [[X_LOBIT:%.*]] = lshr <2 x i64> [[X]], <i64 63, i64 63>
-; CHECK-NEXT:    [[D:%.*]] = zext <2 x i1> [[B]] to <2 x i64>
-; CHECK-NEXT:    [[E:%.*]] = or <2 x i64> [[X_LOBIT]], [[D]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne <2 x i64> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    [[E:%.*]] = zext <2 x i1> [[TMP1]] to <2 x i64>
 ; CHECK-NEXT:    ret <2 x i64> [[E]]
 ;
   %A = icmp slt <2 x i64> %x, <i64 0,i64 0>
   %B = icmp sgt <2 x i64> %x, <i64 0,i64 0>
   %C = zext <2 x i1> %A to <2 x i64>
   %D = zext <2 x i1> %B to <2 x i64>
   %E = or <2 x i64> %C, %D
   ret <2 x i64> %E
 }
+
+
+define <2 x i64> @icmp_slt_0_or_icmp_sgt_0_i64x2_neg(<2 x i64> %x) {
+; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i64x2_neg(
+; CHECK-NEXT:    [[B:%.*]] = icmp sgt <2 x i64> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    [[C:%.*]] = lshr <2 x i64> [[X]], <i64 62, i64 62>
+; CHECK-NEXT:    [[D:%.*]] = zext <2 x i1> [[B]] to <2 x i64>
+; CHECK-NEXT:    [[E:%.*]] = or <2 x i64> [[C]], [[D]]
+; CHECK-NEXT:    ret <2 x i64> [[E]]
+;
+  %B = icmp sgt <2 x i64> %x, zeroinitializer
+  %C = lshr <2 x i64> %x, <i64 62, i64 62>
+  %D = zext <2 x i1> %B to <2 x i64>
+  %E = or <2 x i64> %C, %D
+  ret <2 x i64> %E
+
+}