[InstCombine] enhance icmp with sub folds

[Allen]

Summary

The new IR with And removes a use of the input variable, which is better for analysis.

[goldstein.w.n]

llvm/test/Transforms/InstCombine/icmp-sub.ll

564

Can you split the tests into two commits so we can see the diff from the patch?

[goldstein.w.n]

The new IR with and removes a use of the input variable, which is better for analysis.

"and" -> And (otherwise it looks like the conjugation, not the operator.

[Allen]

1、Precommit the test
2、Add m_OneUse

[Allen]

In D145846#4200141, @goldstein.w.n wrote:

The new IR with and removes a use of the input variable, which is better for analysis.

"and" -> And (otherwise it looks like the conjugation, not the operator.

Done, thanks

llvm/test/Transforms/InstCombine/icmp-sub.ll

564

Done, I Precommit the test with D146268

[Allen]

ping ?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4096

Use ICmpInst::isEquality().

4098

Please add a vector test, this is probably going to crash. (Can use getScalarSizeInBits instead.)

4103

I.getPrediate() -> Pred.

llvm/test/Transforms/InstCombine/icmp-sub.ll

590

Missing commuted test case (negation on RHS), multi-use test case and negative tests (e.g. non-equality predicate).

[Allen]

address commet
1、Add more cases (also update on D146268)
2、update with getScalarSizeInBits and add related vector case
3、use ICmpInst::isEquality(Pred) to replace Pred == ICmpInst::ICMP_EQ
4、I.getPredicate() --> Pred

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4096

isEquality() means "EQ" or "NE". You don't need to check for ICMP_NE separately.

llvm/test/Transforms/InstCombine/icmp-sub.ll

596

These end up not actually commuted due to complexity-based canonicalization. Grep for thwart complexity-based canonicalization for how to avoid it.

[Allen]

Address comment
1、delete the repeat ICMP_NE check, as isEquality() already include it
2、use "thwart complexity-based canonicalization" for commuted case

[nikic]

LGTM

[nikic]

Proof: https://alive2.llvm.org/ce/z/VNNPeG

[bcl5980]

How about this pattern ?
https://alive2.llvm.org/ce/z/Y-Po8g
Also reduce one usage but it works for any minuend.

[Allen]

https://github.com/llvm/llvm-project/issues/60818

In D145846#4266860, @bcl5980 wrote:

How about this pattern ?
https://alive2.llvm.org/ce/z/Y-Po8g
Also reduce one usage but it works for any minuend.

Yes, I think this case is similar, but it seems the llvm doesn't have the issue end-to-end for C source, https://godbolt.org/z/EYMo9bd9c.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4096

Apply your comment, thanks

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

   // If we replaced the mul, erase it. Do this after all uses of Builder,
   // as the mul is used as insertion point.
   if (MulHadOtherUses)
     eraseInstFromFunction(*Mul);
 
   return Res;
 }
 
-static Instruction *foldICmpXNegX(ICmpInst &I) {
+static Instruction *foldICmpXNegX(ICmpInst &I,
+                                  InstCombiner::BuilderTy &Builder) {
   CmpInst::Predicate Pred;
   Value *X;
-  if (!match(&I, m_c_ICmp(Pred, m_NSWNeg(m_Value(X)), m_Deferred(X))))
-    return nullptr;
+  if (match(&I, m_c_ICmp(Pred, m_NSWNeg(m_Value(X)), m_Deferred(X)))) {
 
     if (ICmpInst::isSigned(Pred))
       Pred = ICmpInst::getSwappedPredicate(Pred);
     else if (ICmpInst::isUnsigned(Pred))
       Pred = ICmpInst::getSignedPredicate(Pred);
     // else for equality-comparisons just keep the predicate.
 
     return ICmpInst::Create(Instruction::ICmp, Pred, X,
                             Constant::getNullValue(X->getType()), I.getName());
+  }
+
+  // A value is not equal to its negation unless that value is 0 or
+  // MinSignedValue, ie: a != -a --> (a & MaxSignedVal) != 0
+  if (match(&I, m_c_ICmp(Pred, m_OneUse(m_Neg(m_Value(X))), m_Deferred(X))) &&
+      (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_EQ)) {
+    Type *Ty = X->getType();
+    uint32_t BitWidth = cast<IntegerType>(Ty)->getBitWidth();
+    Constant *MaxSignedVal =
+        ConstantInt::get(Ty, APInt::getSignedMaxValue(BitWidth));
+    Value *And = Builder.CreateAnd(X, MaxSignedVal);
+    Constant *Zero = Constant::getNullValue(Ty);
+    return CmpInst::Create(Instruction::ICmp, I.getPredicate(), And, Zero);
+  }
+
+  return nullptr;
 }
 
 /// Try to fold icmp (binop), X or icmp X, (binop).
 /// TODO: A large part of this logic is duplicated in InstSimplify's
 /// simplifyICmpWithBinOp(). We should be able to share that and avoid the code
 /// duplication.
 Instruction *InstCombinerImpl::foldICmpBinOp(ICmpInst &I,
                                              const SimplifyQuery &SQ) {
   const SimplifyQuery Q = SQ.getWithInstruction(&I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   // Special logic for binary operators.
   BinaryOperator *BO0 = dyn_cast<BinaryOperator>(Op0);
   BinaryOperator *BO1 = dyn_cast<BinaryOperator>(Op1);
   if (!BO0 && !BO1)
     return nullptr;
 
-  if (Instruction *NewICmp = foldICmpXNegX(I))
+  if (Instruction *NewICmp = foldICmpXNegX(I, Builder))
     return NewICmp;
 
   const CmpInst::Predicate Pred = I.getPredicate();
   Value *X;
 
   // Convert add-with-unsigned-overflow comparisons into a 'not' with compare.
   // (Op1 + X) u</u>= Op1 --> ~Op1 u</u>= X
   if (match(Op0, m_OneUse(m_c_Add(m_Specific(Op1), m_Value(X)))) &&

llvm/test/Transforms/InstCombine/icmp-sub.ll

   %phi_outer = phi i32 [ %sub, %bb_loop ], [ %x, %bb_entry ]
   %sub = sub i32 %phi_outer, %y
   %cond_outer = icmp eq i32 %sub, 0
   br i1 %cond_outer, label %bb_exit, label %bb_loop
 
 bb_exit:
   ret void
 }
 
 ; https://alive2.llvm.org/ce/z/D2Aph4
 define i1 @PR60818_ne(i32 %a) {
 ; CHECK-LABEL: @PR60818_ne(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[A:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[SUB]], [[A]]
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[A:%.*]], 2147483647
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP0]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
 entry:
   %sub = sub i32 0, %a
   %cmp = icmp ne i32 %sub, %a
   ret i1 %cmp
 }
 
 define i1 @PR60818_eq(i32 %a) {
 ; CHECK-LABEL: @PR60818_eq(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[A:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[SUB]], [[A]]
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[A:%.*]], 2147483647
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP0]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
 entry:
   %sub = sub i32 0, %a
   %cmp = icmp eq i32 %sub, %a
   ret i1 %cmp
 }