[InstCombine] Fold signbit test of a pow2 or zero

[junaire]

Summary

Alive2: https://alive2.llvm.org/ce/z/_J5q3S
Closes: https://github.com/llvm/llvm-project/issues/60957

Signed-off-by: Jun Zhang <[e-mail]>

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1343

There are other power of 2 patterns. Maybe use isKnownPowerOf2?

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1343

disregard, misunderstood the patch.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1343

m_Sub(m_Zero(), m_Value(X)) -> m_Neg(m_Value(X))?
Also do you need m_OneUse? This shouldn't ever create more instructions.

[junaire]

Address comments.

[junaire]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1343

Also do you need m_OneUse? This shouldn't ever create more instructions.

I thought it was unnecessary at first, but then it cause a regression in smax_xor_pow2_neg,
so I added it.

@@ -137,7 +137,10 @@ define i8 @smax_xor_pow2_neg(i8 %x, i8 %y) {                                                                                      ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[Y:%.*]], -128                                                                                             ; CHECK-NEXT:    br i1 [[CMP]], label [[NEG:%.*]], label [[POS:%.*]]                                                                                  ; CHECK:       neg:                                                                                                                                  -; CHECK-NEXT:    [[R:%.*]] = and i8 [[X:%.*]], 127                                                                                                   +; CHECK-NEXT:    [[NY:%.*]] = sub i8 0, [[Y]]                                                                                                        +; CHECK-NEXT:    [[YP2:%.*]] = and i8 [[NY]], [[Y]]                                                                                                  +; CHECK-NEXT:    [[X_XOR:%.*]] = xor i8 [[YP2]], [[X:%.*]]                                                                                           +; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.smax.i8(i8 [[X]], i8 [[X_XOR]])                                                                            ; CHECK-NEXT:    ret i8 [[R]]                                                                                                                         ; CHECK:       pos:                                                                                                                                   ; CHECK-NEXT:    call void @barrier()

[junaire]

Update the comment.

[RKSimon]

Please can you add vector test coverage?

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1343

Use m_c_And (and add suitable test coverage)?

[junaire]

Address comments, thanks @RKSimon

[junaire]

In D144777#4153394, @RKSimon wrote:

Please can you add vector test coverage?

Oops, missed this comment, will do.

[spatel]

llvm/test/Transforms/InstCombine/fold-signbit-test-power2.ll

14

Ths isn't testing what you expected because the and operands will be commuted before they reach the transform in this patch. This would be easier to see if you pre-commit the tests with baseline results (no pre-commit Phab review is needed for that NFC change).

grep for "thwart complexity-based canonicalization" in the test directory to see how to create a test that handles the commuted pattern.

36

See comment about commuting - same as above.

[junaire]

Add vevtor tests.

[junaire]

Hi @spatel, thanks for your comments, I updated the tests according to your
suggestions. However, everything stop folding after I use div instructions to
each oprands of and instruction.

Can you take a look? Is this because I missed something? Or my fold pattern is wrong.

[spatel]

In D144777#4153685, @junaire wrote:

Hi @spatel, thanks for your comments, I updated the tests according to your
suggestions. However, everything stop folding after I use div instructions to
each oprands of and instruction.

Can you take a look? Is this because I missed something? Or my fold pattern is wrong.

There shouldn't be any extra instruction between the sub (negate) and and. You just need one extra binary-op instruction to create "%x", so it stays operand 0 of the and. You don't need any extra instructions if you want "%x" to be operand 1.

I think it would be better to add the transform inside of InstCombinerImpl::foldICmpAndConstant().

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1341

"CI" should be "MinSignedC" or something like that in these comments and the code to be more specific.

[junaire]

Rebase

[junaire]

In D144777#4154057, @spatel wrote:

In D144777#4153685, @junaire wrote:

Hi @spatel, thanks for your comments, I updated the tests according to your
suggestions. However, everything stop folding after I use div instructions to
each oprands of and instruction.

Can you take a look? Is this because I missed something? Or my fold pattern is wrong.

There shouldn't be any extra instruction between the sub (negate) and and. You just need one extra binary-op instruction to create "%x", so it stays operand 0 of the and. You don't need any extra instructions if you want "%x" to be operand 1.

I think it would be better to add the transform inside of InstCombinerImpl::foldICmpAndConstant().

Thanks for your comments, they are very helpful. I pushed an NFC change about the recommit test in https://github.com/llvm/llvm-project/commit/cf491a165f239abfa7ab9e707f5cbd1861a6cb20 and moved the fold pattern to the place you suggest.

Please take a look :)

[spatel]

We should have 2 more tests: (1) extra use of the sub and (2) extra use of the and.
As noted earlier, this patch should not require a "m_OneUse" limitation. I realize that it looks like a regression for the existing test, but that should be ok when viewed globally: we are reducing to an equality compare, and GVN, CVP, or some other pass will reduce that to the optimal form. It's just lucky (or unlucky) that the min/max folds added with D144606 are able to reduce it all within InstCombine.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1853

Formatting:

Value *X;

llvm/test/Transforms/InstCombine/fold-signbit-test-power2.ll

5

It's easier to follow the test progression if we make the test names slightly more specific.
This is a signbit test for "isNegative", so "pow2_or_zero_is_negative".
To provide a little more coverage, you could change some of the tests to include variations of that like:

define i1 @pow2_or_zero_is_negative(i8 %x) {
  %negx = sub i8 0, %x
  %pow2_or_zero = and i8 %negx, %x 
  %cmp = icmp ugt i8 %pow2_or_zero, 127
  ret i1 %cmp
}

That should already fold as expected without having to change anything in this patch, but it's good to show that we can handle it.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1826

Re-use this logic (put the new code inside of here)?

[junaire]

Reuse existing code and add more tests.

Just a beginer to the middle-end so bear with me if I get things wrong!

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1835–1836

It could go either way, but I prefer "C"-style notation (consistent with the comment above) for its compactness:

// (X & -X) <  0 --> X == MinSignedC
// (X & -X) > -1 --> X != MinSignedC

llvm/test/Transforms/InstCombine/fold-signbit-test-power2.ll

58

This is "is_not_negative"

105

Let's not duplicate everything for unsigned predicates. It's sufficient to change one or two of the above tests to confirm that we handle the various forms of signbit tests.

[junaire]

Update tests.

[junaire]

Update tests.

[junaire]

Update tests

[junaire]

Make sure the comments are properly aligned!

[spatel]

LGTM - thanks!
See inline comments for a small adjustment to the tests.

llvm/test/Transforms/InstCombine/fold-signbit-test-power2.ll

15

I'd rather not add this "is_not_negative / ult" instruction to this test. It is confusing given the test name.

40

I'd rather not add this "is_not_negative / ult" instruction to this test. It is confusing given the test name.

[junaire]

Update

[junaire]

Thanks to everyone who helped me review the patch! My first contribution to the optimization world, nice!

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpWithConstant(ICmpInst &Cmp) {
   Value *A, *B;
   ConstantInt *CI, *CI2; // I = icmp ugt (add (add A, B), CI2), CI
   if (Pred == ICmpInst::ICMP_UGT && match(Op1, m_ConstantInt(CI)) &&
       match(Op0, m_Add(m_Add(m_Value(A), m_Value(B)), m_ConstantInt(CI2))))
     if (Instruction *Res = processUGT_ADDCST_ADD(Cmp, A, B, CI2, CI, *this))
       return Res;
 
   // icmp(phi(C1, C2, ...), C) -> phi(icmp(C1, C), icmp(C2, C), ...).
   Constant *C = dyn_cast<Constant>(Op1);
   if (!C)
     return nullptr;
 
   if (auto *Phi = dyn_cast<PHINode>(Op0))
     if (all_of(Phi->operands(), [](Value *V) { return isa<Constant>(V); })) {
       Type *Ty = Cmp.getType();
       Builder.SetInsertPoint(Phi);
       PHINode *NewPhi =
           Builder.CreatePHI(Ty, Phi->getNumOperands());
       for (BasicBlock *Predecessor : predecessors(Phi->getParent())) {

 Instruction *InstCombinerImpl::foldICmpAndConstant(ICmpInst &Cmp,
                                                    BinaryOperator *And,
                                                    const APInt &C) {
   if (Instruction *I = foldICmpAndConstConst(Cmp, And, C))
     return I;
 
   const ICmpInst::Predicate Pred = Cmp.getPredicate();
   bool TrueIfNeg;
   if (isSignBitCheck(Pred, C, TrueIfNeg)) {
     // ((X - 1) & ~X) <  0 --> X == 0
     // ((X - 1) & ~X) >= 0 --> X != 0
     Value *X;
     if (match(And->getOperand(0), m_Add(m_Value(X), m_AllOnes())) &&
         match(And->getOperand(1), m_Not(m_Specific(X)))) {
       auto NewPred = TrueIfNeg ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
       return new ICmpInst(NewPred, X, ConstantInt::getNullValue(X->getType()));
     }
   }
 
   // TODO: These all require that Y is constant too, so refactor with the above.
 
   // Try to optimize things like "A[i] & 42 == 0" to index computations.
   Value *X = And->getOperand(0);
   Value *Y = And->getOperand(1);
   if (auto *C2 = dyn_cast<ConstantInt>(Y))
     if (auto *LI = dyn_cast<LoadInst>(X))
       if (auto *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0)))
         if (auto *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)))
           if (Instruction *Res =
                   foldCmpLoadFromIndexedGlobal(LI, GEP, GV, Cmp, C2))
             return Res;
 
+  // icmp slt (and -X, X), 0 --> icmp eq (X, MinSignedC)
+  // icmp sgt (and -X, X), -1 --> icmp ne (X, MinSignedC)
+  {
+    Value* X;
+    if (match(And, m_OneUse(m_c_And(m_Neg(m_Value(X)), m_Deferred(X))))) {
+      Constant *MinSignedC = ConstantInt::get(
+          X->getType(),
+          APInt::getSignedMinValue(X->getType()->getScalarSizeInBits()));
+      if (Pred == ICmpInst::ICMP_SLT && C.isZero())
+        return new ICmpInst(ICmpInst::ICMP_EQ, X, MinSignedC);
+      if (Pred == ICmpInst::ICMP_SGT && C.isAllOnes())
+        return new ICmpInst(ICmpInst::ICMP_NE, X, MinSignedC);
+    }
+  }
+
   if (!Cmp.isEquality())
     return nullptr;
 
   // X & -C == -C -> X >  u ~C
   // X & -C != -C -> X <= u ~C
   //   iff C is a power of 2
   if (Cmp.getOperand(1) == Y && C.isNegatedPowerOf2()) {
     auto NewPred =

llvm/test/Transforms/InstCombine/fold-signbit-test-power2.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 ; icmp slt (and X, -X), 0 --> icmp eq (X, MinSignC)
 define i1 @pow2_or_zero1(i8 %x) {
 ; CHECK-LABEL: @pow2_or_zero1(
-; CHECK-NEXT:    [[NEG:%.*]] = sub i8 0, [[X:%.*]]
-; CHECK-NEXT:    [[POW2_OR_ZERO:%.*]] = and i8 [[NEG]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[POW2_OR_ZERO]], 0
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], -128
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %neg = sub i8 0, %x
   %pow2_or_zero = and i8 %x, %neg
   %cmp = icmp slt i8 %pow2_or_zero, 0
   ret i1 %cmp
 }
 
 ; icmp slt (and -X, X), 0 --> icmp eq (X, MinSignC)
 define i1 @pow2_or_zero1_commute(i8 %A) {
 ; CHECK-LABEL: @pow2_or_zero1_commute(
-; CHECK-NEXT:    [[X:%.*]] = sdiv i8 42, [[A:%.*]]
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw i8 0, [[X]]
-; CHECK-NEXT:    [[POW2_OR_ZERO:%.*]] = and i8 [[X]], [[NEG]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[POW2_OR_ZERO]], 0
+; CHECK-NEXT:    [[X:%.*]] = mul i8 [[A:%.*]], 42
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X]], -128
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
-  %x = sdiv i8 42, %A ; thwart complexity-based canonicalization
+  %x = mul i8 42, %A ; thwart complexity-based canonicalization
   %neg = sub i8 0, %x
   %pow2_or_zero = and i8 %neg, %x
   %cmp = icmp slt i8 %pow2_or_zero, 0
   ret i1 %cmp
 }
 
 define <2 x i1> @pow2_or_zero1_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @pow2_or_zero1_vec(
-; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i8> zeroinitializer, [[X:%.*]]
-; CHECK-NEXT:    [[POW2_OR_ZERO:%.*]] = and <2 x i8> [[NEG]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> [[POW2_OR_ZERO]], zeroinitializer
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i8> [[X:%.*]], <i8 -128, i8 -128>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %neg = sub <2 x i8> <i8 0, i8 0>, %x
   %pow2_or_zero = and <2 x i8> %x, %neg
   %cmp = icmp slt <2 x i8> %pow2_or_zero, <i8 0, i8 0>
   ret <2 x i1> %cmp
 }
 
 
 define <2 x i1> @pow2_or_zero1_vec_commute(<2 x i8> %A) {
 ; CHECK-LABEL: @pow2_or_zero1_vec_commute(
 ; CHECK-NEXT:    [[X:%.*]] = mul <2 x i8> [[A:%.*]], <i8 42, i8 42>
-; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i8> zeroinitializer, [[X]]
-; CHECK-NEXT:    [[POW2_OR_ZERO:%.*]] = and <2 x i8> [[X]], [[NEG]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> [[POW2_OR_ZERO]], zeroinitializer
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i8> [[X]], <i8 -128, i8 -128>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %x = mul <2 x i8> <i8 42, i8 42>, %A ; thwart complexity-based canonicalization
   %neg = sub <2 x i8> <i8 0, i8 0>, %x
   %pow2_or_zero = and <2 x i8> %neg, %x
   %cmp = icmp slt <2 x i8> %pow2_or_zero, <i8 0, i8 0>
   ret <2 x i1> %cmp
 }
 
 ; icmp sgt (and X, -X), -1 --> icmp ne (X, MinSignC)
 define i1 @pow2_or_zero2(i8 %x) {
 ; CHECK-LABEL: @pow2_or_zero2(
-; CHECK-NEXT:    [[NEG:%.*]] = sub i8 0, [[X:%.*]]
-; CHECK-NEXT:    [[POW2_OR_ZERO:%.*]] = and i8 [[NEG]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[POW2_OR_ZERO]], -1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[X:%.*]], -128
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %neg = sub i8 0, %x
   %pow2_or_zero = and i8 %x, %neg
   %cmp = icmp sgt i8 %pow2_or_zero, -1
   ret i1 %cmp
 }
 
 ; icmp sgt (and -X, X), -1 --> icmp ne (X, MinSignC)
 define i1 @pow2_or_zero2_commute(i8 %A) {
 ; CHECK-LABEL: @pow2_or_zero2_commute(
 ; CHECK-NEXT:    [[X:%.*]] = mul i8 [[A:%.*]], 42
-; CHECK-NEXT:    [[NEG:%.*]] = sub i8 0, [[X]]
-; CHECK-NEXT:    [[POW2_OR_ZERO:%.*]] = and i8 [[X]], [[NEG]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[POW2_OR_ZERO]], -1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[X]], -128
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %x = mul i8 42, %A ; thwart complexity-based canonicalization
   %neg = sub i8 0, %x
   %pow2_or_zero = and i8 %neg, %x
   %cmp = icmp sgt i8 %pow2_or_zero, -1
   ret i1 %cmp
 }
 
 define <2 x i1> @pow2_or_zero2_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @pow2_or_zero2_vec(
-; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i8> zeroinitializer, [[X:%.*]]
-; CHECK-NEXT:    [[POW2_OR_ZERO:%.*]] = and <2 x i8> [[NEG]], [[X]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i8> [[POW2_OR_ZERO]], <i8 -1, i8 -1>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[X:%.*]], <i8 -128, i8 -128>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %neg = sub <2 x i8> <i8 0, i8 0>, %x
   %pow2_or_zero = and <2 x i8> %x, %neg
   %cmp = icmp sgt <2 x i8> %pow2_or_zero, <i8 -1, i8 -1>
   ret <2 x i1> %cmp
 }
 
 define <2 x i1> @pow2_or_zero2_vec_commute(<2 x i8> %A) {
 ; CHECK-LABEL: @pow2_or_zero2_vec_commute(
 ; CHECK-NEXT:    [[X:%.*]] = mul <2 x i8> [[A:%.*]], <i8 42, i8 42>
-; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i8> zeroinitializer, [[X]]
-; CHECK-NEXT:    [[POW2_OR_ZERO:%.*]] = and <2 x i8> [[X]], [[NEG]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i8> [[POW2_OR_ZERO]], <i8 -1, i8 -1>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[X]], <i8 -128, i8 -128>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %x = mul <2 x i8> <i8 42, i8 42>, %A ; thwart complexity-based canonicalization
   %neg = sub <2 x i8> <i8 0, i8 0>, %x
   %pow2_or_zero = and <2 x i8> %neg, %x
   %cmp = icmp sgt <2 x i8> %pow2_or_zero, <i8 -1, i8 -1>
   ret <2 x i1> %cmp
 }

llvm/test/Transforms/InstCombine/minmax-of-xor-x.ll

;
   %yp2 = and <2 x i8> %y, %ny
   %x_xor = xor <2 x i8> %x, %yp2
   %r = call <2 x i8> @llvm.smin.v2i8(<2 x i8> %x, <2 x i8> %x_xor)
   ret <2 x i8> %r
 }
 
 define i8 @smax_xor_pow2_neg(i8 %x, i8 %y) {
 ; CHECK-LABEL: @smax_xor_pow2_neg(
-; CHECK-NEXT:    [[NY:%.*]] = sub i8 0, [[Y:%.*]]
-; CHECK-NEXT:    [[YP2:%.*]] = and i8 [[NY]], [[Y]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[YP2]], 0
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[Y:%.*]], -128
 ; CHECK-NEXT:    br i1 [[CMP]], label [[NEG:%.*]], label [[POS:%.*]]
 ; CHECK:       neg:
 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[X:%.*]], 127
 ; CHECK-NEXT:    ret i8 [[R]]
 ; CHECK:       pos:
 ; CHECK-NEXT:    call void @barrier()
 ; CHECK-NEXT:    ret i8 0
 ;