[InstSimplify] Odd - X ==/!= X -> false/true

[nikic]

Please provide an alive proof and add tests for other predicates as well, as well as negative tests (e.g. 2 instead of 1, which should not fold).

[liaolucy]

In D132989#3760367, @nikic wrote:

Please provide an alive proof and add tests for other predicates as well, as well as negative tests (e.g. 2 instead of 1, which should not fold).

https://alive2.llvm.org/ce/z/DJqxNZ try to add alive, please correct me if it's not correct

[spatel]

Move this to InstSimplify rather than InstCombine. It should handle both equality preds at least (eq and ne). You should not create a fake instruction - create the expected constant directly.

[spatel]

In D132989#3760397, @liaolucy wrote:

https://alive2.llvm.org/ce/z/DJqxNZ try to add alive, please correct me if it's not correct

I think we can generalize the transform at least in one direction - the constant does not have to be 1:
https://alive2.llvm.org/ce/z/bPYNJT
(not sure if there's some other relationship for non-equality predicates)

[liaolucy]

iupdate to InstSimplify, transform:
(sub nsw|nuw C, X) == X, C is odd --> false
https://alive2.llvm.org/ce/z/dyn2Z2

(sub nsw|nuw C, X) != X, C is odd --> true
https://alive2.llvm.org/ce/z/5aSkqc

(sub 1, X) == X --> false
(sub 1, X) != X --> true
https://alive2.llvm.org/ce/z/DJqxNZ

[liaolucy]

I think we can generalize the transform at least in one direction - the constant does not have to be 1:
https://alive2.llvm.org/ce/z/bPYNJT
(not sure if there's some other relationship for non-equality predicates)

I am trying to understand the example， get odd constant value from more instructions(>1), I don't know how to implement it, any suggestions?

[spatel]

In D132989#3766063, @liaolucy wrote:

I think we can generalize the transform at least in one direction - the constant does not have to be 1:
https://alive2.llvm.org/ce/z/bPYNJT
(not sure if there's some other relationship for non-equality predicates)

I am trying to understand the example， get odd constant value from more instructions(>1), I don't know how to implement it, any suggestions?

The proof just shows that the transform is valid for any value with low-bit cleared.

If the value is a constant, then it is easy to detect. If the value is not constant, then we have to try more expensive (in compile-time) analysis - see ValueTracking's computeKnownBits() for example.

If we do not have a real-world example that shows the more expensive transform is needed, then we should not add it. In other words, the patch is mostly fine as implemented. But I do not understand why we have no-wrap requirements. The transform is correct without those:
https://alive2.llvm.org/ce/z/h4ZFVD

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

570 ↗

(On Diff #457491)

No need to include "entry" label in a minimum test like this.

572 ↗

(On Diff #457491)

What happens if %sub and %x are swapped in this test?

576 ↗

(On Diff #457491)

Change this to a vector type to confirm that the transform works in that case too. We should have one test where the vector constant includes a "poison" element too.

587 ↗

(On Diff #457491)

We need at least one negative test with an even constant. That shows that the transform is not happening when it should not.

[spatel]

In D132989#3766811, @spatel wrote:

The proof just shows that the transform is valid for any value with low-bit cleared.

Sorry - that was supposed to be "any value with low-bit set".

[liaolucy]

1. Add more test case.
2. Delete no-wrap check.

[liaolucy]

If we do not have a real-world example that shows the more expensive transform is needed, then we should not add it. In other words, the patch is mostly fine as implemented. But I do not understand why we have no-wrap requirements. The transform is correct without those:
https://alive2.llvm.org/ce/z/h4ZFVD

Actually, I'm not sure if just using srem(2) is correct.

[spatel]

In D132989#3766992, @liaolucy wrote:

If we do not have a real-world example that shows the more expensive transform is needed, then we should not add it. In other words, the patch is mostly fine as implemented. But I do not understand why we have no-wrap requirements. The transform is correct without those:
https://alive2.llvm.org/ce/z/h4ZFVD

Actually, I'm not sure if just using srem(2) is correct.

I think it would be a little more efficient/readable to code this as "*C & 1".

But we need to be certain that the transform is correct to proceed. Do you have a counter-example that shows an incorrect result?

[liaolucy]

Use *C & 1 to find odd constant value

[RKSimon]

llvm/lib/Analysis/InstructionSimplify.cpp

3310

Can we use knownbits here instead to support non-uniform constant vectors?

I'm never very clear on when we're allowed to use value tracking in instsimplify as its more expensive....

[spatel]

1. Did you determine that the transform is valid without nsw/nuw?

2. My request for a vector test with poison element was not handled. Please mark inline questions as completed when they are answered.

3. The tests should be in the tests/Transforms/InstSimplify directory, and the RUN line should only use -instsimplify.

llvm/lib/Analysis/InstructionSimplify.cpp

3308–3309

Reduce to match() with m_Specific()?

3310

Yes, I mentioned that in an earlier comment.

I think we could handle the non-uniform constant pattern even without knownbits - check the compare of a constant expression? But I'd say let's do that as a follow-up to keep this patch simpler.

[liaolucy]

1. Move testcases to tests/Transforms/InstSimplify
2. Use m_Specific

[liaolucy]

In D132989#3769189, @spatel wrote:

1. Did you determine that the transform is valid without nsw/nuw?

Yes, it is correct without nsw/nuw, some testcases have been added.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

3254–3261

Can you add this match inside of simplifyICmpWithBinOpOnLHS()? Then the swapped pattern is handled automatically.

3308

The nullptr and equality checks are redundant - that is handled by the match().

llvm/test/Transforms/InstSimplify/icmp.ll

215

Please pre-commit the baseline tests and then update this patch so it shows the diffs.

[liaolucy]

Move to simplifyICmpWithBinOpOnLHS()

[liaolucy]

address comments , thanks spatel. rebase.

[spatel]

LGTM

llvm/lib/Analysis/InstructionSimplify.cpp

3134

This can be shortened like the code above:

return getFalse(ITy);
...
return getTrue(ITy);

[liaolucy]

llvm/lib/Analysis/InstructionSimplify.cpp

3134

456c7ef68e13b9dedd12a2333e01b6fdbc534b0a

3134

https://reviews.llvm.org/rG456c7ef68e13b9dedd12a2333e01b6fdbc534b0a done, sorry I didn't read it carefully

llvm/lib/Analysis/InstructionSimplify.cpp

if ((match(LBO, m_UDiv(m_Mul(m_Specific(RHS), m_APInt(C1)), m_APInt(C2))) &&
       (match(LBO, m_UDiv(m_Shl(m_Specific(RHS), m_APInt(C1)), m_APInt(C2))) &&
        (APInt(C1->getBitWidth(), 1) << *C1).ule(*C2))) {
     if (Pred == ICmpInst::ICMP_UGT)
       return getFalse(ITy);
     if (Pred == ICmpInst::ICMP_ULE)
       return getTrue(ITy);
   }
 
+  // (sub C, X) == X, C is odd  --> false
+  // (sub C, X) != X, C is odd  --> true
+  if (match(LBO, m_Sub(m_APInt(C), m_Specific(RHS)))) {
+    if ((*C & 1) == 1) {
+      if (Pred == CmpInst::ICMP_EQ)
+        return ConstantInt::getFalse(getCompareTy(RHS));
+      if (Pred == CmpInst::ICMP_NE)
+        return ConstantInt::getTrue(getCompareTy(RHS));
+    }
+  }
+
   return nullptr;
 }
 
 // If only one of the icmp's operands has NSW flags, try to prove that:
 //
 //   icmp slt (x + C1), (x +nsw C2)
 //
 // is equivalent to:
if (A && C && (A == C || A == D || B == C || B == D) && CanSimplify) {
         Y = A;
         Z = C;
       }
       if (Value *V = simplifyICmpInst(Pred, Y, Z, Q, MaxRecurse - 1))
         return V;
     }
   }
 
   if (LBO)
     if (Value *V = simplifyICmpWithBinOpOnLHS(Pred, LBO, RHS, Q, MaxRecurse))
       return V;
 
   if (RBO)
     if (Value *V = simplifyICmpWithBinOpOnLHS(
             ICmpInst::getSwappedPredicate(Pred), RBO, LHS, Q, MaxRecurse))
       return V;
 
   // 0 - (zext X) pred C
   if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) {
     const APInt *C;
     if (match(RHS, m_APInt(C))) {
       if (C->isStrictlyPositive()) {
         if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_NE)
           return ConstantInt::getTrue(getCompareTy(RHS));
if (Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(LBO)) ||
         return ConstantInt::getFalse(getCompareTy(RHS));
       if (Pred == ICmpInst::ICMP_NE)
         return ConstantInt::getTrue(getCompareTy(RHS));
     }
   }
 
   // TODO: This is overly constrained. LHS can be any power-of-2.
   // (1 << X)  >u 0x8000 --> false
   // (1 << X) <=u 0x8000 --> true
   if (match(LHS, m_Shl(m_One(), m_Value())) && match(RHS, m_SignMask())) {
     if (Pred == ICmpInst::ICMP_UGT)
       return ConstantInt::getFalse(getCompareTy(RHS));
     if (Pred == ICmpInst::ICMP_ULE)
       return ConstantInt::getTrue(getCompareTy(RHS));
   }
 
   if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() &&
       LBO->getOperand(1) == RBO->getOperand(1)) {
     switch (LBO->getOpcode()) {

llvm/test/Transforms/InstSimplify/icmp.ll

loop:
   %p1 = phi i32 [ %x, %entry ], [ %sub1, %loop ]
   %p2 = phi i32 [ %x, %entry ], [ %sub2, %loop ]
   %cmp = icmp eq i32 %p1, %p2
   %user = zext i1 %cmp to i32
   %sub1 = sub i32 %p1, %p2
   %sub2 = sub i32 42, %p2
   br label %loop
 }
+
+define i1 @sub_false(i32 %x) {
+; CHECK-LABEL: @sub_false(
+; CHECK-NEXT:    ret i1 false
+;
+  %sub = sub i32 1, %x
+  %cmp = icmp eq i32 %sub, %x
+  ret i1 %cmp
+}
+
+define i1 @sub_swap(i8 %x) {
+; CHECK-LABEL: @sub_swap(
+; CHECK-NEXT:    ret i1 true
+;
+  %sub = sub i8 3, %x
+  %cmp = icmp ne i8 %x, %sub
+  ret i1 %cmp
+}
+
+define <2 x i1> @sub_odd(<2 x i8> %x) {
+; CHECK-LABEL: @sub_odd(
+; CHECK-NEXT:    ret <2 x i1> <i1 true, i1 true>
+;
+  %sub = sub <2 x i8> <i8 3, i8 3>, %x
+  %cmp = icmp ne <2 x i8> %sub, %x
+  ret <2 x i1> %cmp
+}
+
+define <2 x i1> @sub_odd_poison(<2 x i8> %x) {
+; CHECK-LABEL: @sub_odd_poison(
+; CHECK-NEXT:    [[SUB:%.*]] = sub <2 x i8> <i8 poison, i8 1>, [[X:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[SUB]], [[X]]
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %sub = sub <2 x i8> <i8 poison, i8 1>, %x
+  %cmp = icmp ne <2 x i8> %sub, %x
+  ret <2 x i1> %cmp
+}
+
+define i1 @sub_even(i8 %x) {
+; CHECK-LABEL: @sub_even(
+; CHECK-NEXT:    [[SUB:%.*]] = sub i8 2, [[X:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[SUB]], [[X]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %sub = sub i8 2, %x
+  %cmp = icmp ne i8 %sub, %x
+  ret i1 %cmp
+}