[InstCombine] Fold (A/-B)==(A/B) to (A/B)==0

[marcauberer]

Summary

Fixes #62382: https://github.com/llvm/llvm-project/issues/62382

This optimization applies under the precondition, that B is not equal to the minimum
value for the bitwidth of B, e.g. -128 for i8.

Alive2: https://alive2.llvm.org/ce/z/WIiHur
Baseline tests: https://reviews.llvm.org/D159204

[marcauberer]

Rebase

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

3153 ↗

(On Diff #554717)

This at the very least should be a seperate patch and should probably fit into:
IsCondKnownTrue not be its own API.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5234

This comment should include 'if B != INT_MIN'.

5234

Err B != INT_MAX or A != INT_MIN (if you update to also fallback to A check.

5240

m_Deferred -> m_Specific. You aren't rematching A/B in the same match statement.

5241

Can you split the isKnownNonEqual to a new patch and use either IsCondKnownTrue here or probably more direct in this case just use computeKnownBits.

5242

You can strengthen this as it also works if A != INT_MAX: https://alive2.llvm.org/ce/z/MFAjAs so if check for B fails you can tryout A.

[marcauberer]

Apply review feedback

[marcauberer]

llvm/lib/Analysis/ValueTracking.cpp

3153 ↗

(On Diff #554717)

I cannot find IsCondKnownTrue. Where can I find it?

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

3153 ↗

(On Diff #554717)

Crap I pasted the wrong thing. Mean: simplifyICmpInst

[marcauberer]

llvm/lib/Analysis/ValueTracking.cpp

3153 ↗

(On Diff #554717)

I think I don't quite understand ... This newly added function is essentially the same as computeKnownBitsFromAssume or isKnownNonZeroFromAssume just for isKnownNonEqual. Why should this fit into simplifyICmpInst. Isn't this relevant overall for ValueTracking?
I agree regarding the split into a new patch.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5241

How would I do that with computeKnownBits?

The following code does not seem to work, probably due to the fact that the assumption is not made for value A or B, but rather the icmp ne of A/B with MIN_INT:

// Check if A is known to be != INT_MIN
KnownBits KnownA = computeKnownBits(A, 0, &I);
if (KnownA.isConstant() && KnownA.getConstant() == MinInt)
  return new ICmpInst(Pred, Op1, Constant::getNullValue(A->getType()));

[marcauberer]

Rebase

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

3153 ↗

(On Diff #554717)

Sorry I misunderstood an aspect of you patch. Please split this part but you're right it belongs as it is.

[marcauberer]

Rebase onto ValueTracking change

[marcauberer]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5241

@goldstein.w.n ping? Or is this resolved with extracting the isKnownNonEqual part to a new patch? This is done now.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5241

Ah sorry didn't see your earlier message.

You don't really need to/want to be testing isKnownNonEqual here. You want to be testing this particular fold.
which doesn't inherently rely on isKnownNonEqual, it just relies on A/B != INT_MIN.

The latter can sometimes be proven with knownbits, for example (a | 1) == INT_MAX is known always false.

Since the isKnownNonEqual patch will probably take longer to get in, I would suggest doing something like:
!computeKnownBits(A, ...).getSignedMinValue().isMinSignedValue()

[marcauberer]

Use computeKnownBits instead of isKnownNonEqual

[marcauberer]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5241

Done.
I had to adjust the tests a bit, because with the original precondition (A != MIN_INT) we are not able to compute any known bits. If we have A != NOT_MIN_INT, we are.

[marcauberer]

Rebase

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5238

NB: A missing todo is if B is contant and Op1 uses -B.
Can you either add TODO comment or implement that.

[marcauberer]

Add ToDo to cover more cases

[marcauberer]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5238

Added a ToDo.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5239

This is a commutative pattern. Think should either put in a lambda so you can pass op0,op1 then op1,op0 or m_c_ICmp(Pred, Pattern0, Pattern1).

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

55

Can you flip the d1/d2 operands in a few of these tests?

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5239

Actually probably easier is something like:

if(match(Op0, S_Div(m_Value(A), m_Value(B))) && match(Op1, S_Div(m_Specific(A), m_Value(C))) {
D = nullptr;
if(match(B, m_Neg(m_Specific(C)) && Op0->hasOneUse()) {
D = B;
}
else if(match(C, m_Neg(m_Specific(B)) && Op1->hasOneUse()) {
D = C;
}
if(D) {
...
}
}

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpEquality(ICmpInst &I) {
   }
 
   if (match(Op1, m_Xor(m_Value(A), m_Value(B))) && (A == Op0 || B == Op0)) {
     // A == (A^B)  ->  B == 0
     Value *OtherVal = A == Op0 ? B : A;
     return new ICmpInst(Pred, OtherVal, Constant::getNullValue(A->getType()));
   }
 
+  // ((A / -B) == (A / B)) -> ((A / B) == 0)
+  // if known A != INT_MIN or B != INT_MIN
+  // ToDo: Add case where B is constant and Op1 uses -B
+  {
+    if (match(Op0, m_OneUse(m_SDiv(m_Value(A), m_OneUse(m_Neg(m_Value(B)))))) &&
+        match(Op1, m_SDiv(m_Specific(A), m_Specific(B)))) {
+      // Check if A is known to be != INT_MIN
+      if (!computeKnownBits(A, 0, &I).getSignedMinValue().isMinSignedValue())
+        return new ICmpInst(Pred, Op1, Constant::getNullValue(A->getType()));
+      // Check if B is known to be != INT_MIN
+      if (!computeKnownBits(B, 0, &I).getSignedMinValue().isMinSignedValue())
+        return new ICmpInst(Pred, Op1, Constant::getNullValue(A->getType()));
+    }
+  }
+
   // (X&Z) == (Y&Z) -> (X^Y) & Z == 0
   if (match(Op0, m_OneUse(m_And(m_Value(A), m_Value(B)))) &&
       match(Op1, m_OneUse(m_And(m_Value(C), m_Value(D))))) {
     Value *X = nullptr, *Y = nullptr, *Z = nullptr;
 
     if (A == C) {
       X = B;
       Y = D;

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare void @llvm.assume(i1)
 declare void @use.i7(i7)
 declare void @use.i14(i14)
 
 define i1 @icmp_sdiv_sdiv_normal_i8(i8 %x, i8 %C) {
 ; CHECK-LABEL: @icmp_sdiv_sdiv_normal_i8(
 ; CHECK-NEXT:    [[PRECOND:%.*]] = icmp eq i8 [[C:%.*]], 12
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[PRECOND]])
-; CHECK-NEXT:    [[NEGC:%.*]] = sub nsw i8 0, [[C]]
-; CHECK-NEXT:    [[D1:%.*]] = sdiv i8 [[X:%.*]], [[NEGC]]
-; CHECK-NEXT:    [[D2:%.*]] = sdiv i8 [[X]], [[C]]
-; CHECK-NEXT:    [[C:%.*]] = icmp eq i8 [[D1]], [[D2]]
+; CHECK-NEXT:    [[D2:%.*]] = sdiv i8 [[X:%.*]], [[C]]
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i8 [[D2]], 0
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %precond = icmp eq i8 %C, 12
   call void @llvm.assume(i1 %precond)
   %negC = sub i8 0, %C
   %d1 = sdiv i8 %x, %negC
   %d2 = sdiv i8 %x, %C
   %c = icmp eq i8 %d1, %d2
   ret i1 %c
 }
 
 define i1 @icmp_sdiv_sdiv_normal_i64(i64 %x, i64 %C) {
 ; CHECK-LABEL: @icmp_sdiv_sdiv_normal_i64(
 ; CHECK-NEXT:    [[PRECOND:%.*]] = icmp eq i64 [[C:%.*]], -9223372036854775807
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[PRECOND]])
-; CHECK-NEXT:    [[NEGC:%.*]] = sub nsw i64 0, [[C]]
-; CHECK-NEXT:    [[D1:%.*]] = sdiv i64 [[X:%.*]], [[NEGC]]
-; CHECK-NEXT:    [[D2:%.*]] = sdiv i64 [[X]], [[C]]
-; CHECK-NEXT:    [[C:%.*]] = icmp eq i64 [[D1]], [[D2]]
+; CHECK-NEXT:    [[D2:%.*]] = sdiv i64 [[X:%.*]], [[C]]
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i64 [[D2]], 0
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %precond = icmp eq i64 %C, -9223372036854775807 ; off by one
   call void @llvm.assume(i1 %precond)
   %negC = sub i64 0, %C
   %d1 = sdiv i64 %x, %negC
   %d2 = sdiv i64 %x, %C
   %c = icmp eq i64 %d1, %d2
   ret i1 %c
 }
 
 define i1 @icmp_sdiv_sdiv_normal_ne(i6 %x, i6 %C) {
 ; CHECK-LABEL: @icmp_sdiv_sdiv_normal_ne(
 ; CHECK-NEXT:    [[PRECOND:%.*]] = icmp eq i6 [[C:%.*]], 4
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[PRECOND]])
-; CHECK-NEXT:    [[NEGC:%.*]] = sub nsw i6 0, [[C]]
-; CHECK-NEXT:    [[D1:%.*]] = sdiv i6 [[X:%.*]], [[NEGC]]
-; CHECK-NEXT:    [[D2:%.*]] = sdiv i6 [[X]], [[C]]
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i6 [[D1]], [[D2]]
+; CHECK-NEXT:    [[D2:%.*]] = sdiv i6 [[X:%.*]], [[C]]
+; CHECK-NEXT:    [[C:%.*]] = icmp ne i6 [[D2]], 0
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %precond = icmp eq i6 %C, 4
   call void @llvm.assume(i1 %precond)
   %negC = sub i6 0, %C
   %d1 = sdiv i6 %x, %negC
   %d2 = sdiv i6 %x, %C
   %c = icmp ne i6 %d1, %d2
   ret i1 %c
 }
 
 define i1 @icmp_sdiv_sdiv_negative_no_precond(i17 %x, i17 %C) {
 ; CHECK-LABEL: @icmp_sdiv_sdiv_negative_no_precond(
 ; CHECK-NEXT:    [[NEGC:%.*]] = sub i17 0, [[C:%.*]]
 ; CHECK-NEXT:    [[D1:%.*]] = sdiv i17 [[X:%.*]], [[NEGC]]
 ; CHECK-NEXT:    [[D2:%.*]] = sdiv i17 [[X]], [[C]]