[InstCombine] Add two optimizations for mul-and-icmp patterns

[fwolff]

Summary

Fixes PR#40493, and in principle also PR#51551, but the known bits analysis isn't quite smart enough to handle the assume in the example there.

The entire logic for this patch has been discussed in PR#40493, it just seems that nobody has gotten around to implementing it yet.

https://alive2.llvm.org/ce/z/Bp6ZoV
https://alive2.llvm.org/ce/z/htSh_Q

[lebedev.ri]

alive2 proofs?

llvm/test/Transforms/InstCombine/pr40493.ll

1

Precommit tests please

[fwolff]

In D114272#3143702, @lebedev.ri wrote:

alive2 proofs?

@test1: https://alive2.llvm.org/ce/z/BN74k2
@test2: https://alive2.llvm.org/ce/z/3PRnmg
@test2_2: https://alive2.llvm.org/ce/z/FmrCSL

The other tests don't do this transformation.

llvm/test/Transforms/InstCombine/pr40493.ll

1

Do you mean that I should submit this file separately first in a different revision?

[lebedev.ri]

In D114272#3143762, @fwolff wrote:

In D114272#3143702, @lebedev.ri wrote:

alive2 proofs?

@test1: https://alive2.llvm.org/ce/z/BN74k2
@test2: https://alive2.llvm.org/ce/z/3PRnmg
@test2_2: https://alive2.llvm.org/ce/z/FmrCSL

The other tests don't do this transformation.

This only shows that those tests aren't miscompiled, i'm interested in the generalized proof for the actual preconditions.

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1920

(style) Don't use auto - APInt should be enough

1934–1935

Don't use auto

[fwolff]

In D114272#3143765, @lebedev.ri wrote:

This only shows that those tests aren't miscompiled

I know; I thought that's what you wanted because the transformations themselves have already been checked in PR#40493, although the links now appear to be defunct.

Anyway, here are the proofs:
https://alive2.llvm.org/ce/z/Bp6ZoV
https://alive2.llvm.org/ce/z/htSh_Q

[RKSimon]

vector tests?

[lebedev.ri]

Thank you for looking into this.

In D114272#3144667, @RKSimon wrote:

vector tests?

Please add vector tests (with splat constants (all constant elements being the same),
splat with undef (there are 2 constants, so 3 variants - same undef lane in either of the constants, and in all of them)),
non-splat, commit these baseline tests into the llvm repo, and rebase this patch - the diff here should not show the tests as being added, it should show the check lines as being changed.

[spatel]

Note: the existing transform to trunc was removed with f55d1eb3746a , so this patch will need to be updated to account for that.

I suspect we need a "hasOneUse" check on the multiply on at least the first transform in this patch, but we should have tests for those patterns either way. It would be easier to review all the permutations if the tests are pre-committed, and this patch is split in 2 pieces (one for each transform).

[spatel]

llvm/test/Transforms/InstCombine/pr40493.ll

1

This was answered in another comment, but to clarify:

Yes - this means (1) create the tests, (2) auto-generate the baseline (without this code change) CHECK lines, (3) commit that, and (4) rebase this patch so we just see the diffs from the baseline results in this review.

I prefer a pattern-based rather than PR-based file name (it may be possible to just add the tests to an existing file with tests for related transforms). It's also nicer to have descriptive function names rather than the anonymous @test....

Ideally, you can push the baseline tests to the main branch. Have you requested/received commit access yet?
https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access

[lebedev.ri]

@fwolff reverse ping?
This doesn't need any big fundamental changes, just a little rebasing.

[fwolff]

In D114272#3179252, @lebedev.ri wrote:

@fwolff reverse ping?
This doesn't need any big fundamental changes, just a little rebasing.

Yes, sorry for the delay. I've committed the tests and updated the diff now.

[fwolff]

Rebased again. Ping @lebedev.ri

[RKSimon]

@spatel @lebedev.ri Any more comments?

[spatel]

The test coverage still seems lacking to me, and I'm not seeing why we need to create a new multiply. If we assume the right constraints, the first transform should be only a low-bit check?
https://alive2.llvm.org/ce/z/YB_4pn

I'll add some tests and post a draft that handles that part of the problem.

[RKSimon]

@fwolff Please can you rebase this patch?

[fwolff]

In D114272#3299405, @RKSimon wrote:

@fwolff Please can you rebase this patch?

Done!

[spatel]

Of the remaining test diffs:
(1) mul_mask_pow2_ne0_use1 is a multi-use corner case that was added to confirm that we don't go overboard
(2) pr51551 and pr51551_2 are handled with a combination of -bdce and -instcombine: https://godbolt.org/z/xr1e96ceM

Do we still need this patch?

[spatel]

We now handle all of the motivating cases with demanded bits improvements ( 995d400f3a3c ), so this patch can be abandoned.

[RKSimon]

This patch should be unnecessary now

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpAndConstant(ICmpInst &Cmp,
   // X & -C != -C -> X <= u ~C
   //   iff C is a power of 2
   if (Cmp.getOperand(1) == Y && C.isNegatedPowerOf2()) {
     auto NewPred =
         Pred == CmpInst::ICMP_EQ ? CmpInst::ICMP_UGT : CmpInst::ICMP_ULE;
     return new ICmpInst(NewPred, X, SubOne(cast<Constant>(Cmp.getOperand(1))));
   }
 
-  // (X & C2) == 0 -> (trunc X) >= 0
-  // (X & C2) != 0 -> (trunc X) <  0
-  //   iff C2 is a power of 2 and it masks the sign bit of a legal integer type.
   const APInt *C2;
   if (And->hasOneUse() && C.isZero() && match(Y, m_APInt(C2))) {
+    // (X & C2) == 0 -> (trunc X) >= 0
+    // (X & C2) != 0 -> (trunc X) <  0
+    //   iff C2 is a power of 2 and it masks the sign bit of a legal integer
+    //   type.
     int32_t ExactLogBase2 = C2->exactLogBase2();
     if (ExactLogBase2 != -1 && DL.isLegalInteger(ExactLogBase2 + 1)) {
       Type *NTy = IntegerType::get(Cmp.getContext(), ExactLogBase2 + 1);
       if (auto *AndVTy = dyn_cast<VectorType>(And->getType()))
         NTy = VectorType::get(NTy, AndVTy->getElementCount());
       Value *Trunc = Builder.CreateTrunc(X, NTy);
       auto NewPred =
           Pred == CmpInst::ICMP_EQ ? CmpInst::ICMP_SGE : CmpInst::ICMP_SLT;
       return new ICmpInst(NewPred, Trunc, Constant::getNullValue(NTy));
     }
+
+    const APInt *C1;
+    Value *X1;
+    // ((X1 * C1) & C2) ==/!= 0 -> ((X1 * (C1/C2)) & 1) ==/!= 0
+    //   iff C2 is a power of 2 greater than 1 and C1 is a multiple of C2
+    if (match(X, m_Mul(m_Value(X1), m_APInt(C1))) && C2->isPowerOf2() &&
+        !C2->isOne() && (C1->urem(*C2)).isZero()) {
+      const auto NewDiv = C1->udiv(*C2);
+      auto *NewMul =
+          Builder.CreateMul(X1, ConstantInt::get(X1->getType(), NewDiv));
+      auto *NewAnd =
+          Builder.CreateAnd(NewMul, ConstantInt::get(NewMul->getType(), 1));
+      return new ICmpInst(Cmp.getPredicate(), NewAnd, Cmp.getOperand(1));
+    }
+
+    Value *X2;
+    // ((X1 * X2) & C2) ==/!= 0 -> (X1 & C2) ==/!= 0
+    //   iff (C2 + 1) is a power of 2 and (X2 & C2) == 1
+    if (match(X, m_Mul(m_Value(X1), m_Value(X2))) && C2->isMask()) {
+      auto TrailingOnes = C2->countTrailingOnes();
+      auto ExpectedZero =
+          C2->usub_sat(APInt::getOneBitSet(C2->getBitWidth(), 0));
+
+      auto Check = [&](Value *Xi, Value *Xj) -> Instruction * {
+        KnownBits XiKnown = computeKnownBits(Xi, 0, &Cmp);
+        if (XiKnown.One.getLoBits(1).isOne() &&
+            XiKnown.Zero.getLoBits(TrailingOnes) == ExpectedZero) {
+          auto *NewAnd =
+              Builder.CreateAnd(Xj, ConstantInt::get(Xj->getType(), *C2));
+          return new ICmpInst(Cmp.getPredicate(), NewAnd, Cmp.getOperand(1));
+        }
+        return nullptr;
+      };
+
+      if (Instruction *I = Check(X1, X2))
+        return I;
+      if (Instruction *I = Check(X2, X1))
+        return I;
+    }
   }
 
   return nullptr;
 }
 
 /// Fold icmp (or X, Y), C.
 Instruction *InstCombinerImpl::foldICmpOrConstant(ICmpInst &Cmp,
                                                   BinaryOperator *Or,

llvm/test/Transforms/InstCombine/pr40493.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; Test that the optimization described in PR#40493 is performed
+define i1 @test1(i32 %area) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[AREA:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP0]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  %mul = mul i32 %area, 12
+  %rem = and i32 %mul, 4
+  %cmp = icmp eq i32 %rem, 0
+  ret i1 %cmp
+}
+
+define i1 @test1_neg1(i32 %area) {
+; CHECK-LABEL: @test1_neg1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[AREA:%.*]], 11
+; CHECK-NEXT:    [[REM:%.*]] = and i32 [[MUL]], 4
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  %mul = mul i32 %area, 11
+  %rem = and i32 %mul, 4
+  %cmp = icmp eq i32 %rem, 0
+  ret i1 %cmp
+}
+
+define i1 @test1_neg2(i32 %area) {
+; CHECK-LABEL: @test1_neg2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[AREA:%.*]], 12
+; CHECK-NEXT:    [[REM:%.*]] = and i32 [[MUL]], 12
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  %mul = mul i32 %area, 12
+  %rem = and i32 %mul, 15
+  %cmp = icmp eq i32 %rem, 0
+  ret i1 %cmp
+}
+
+define i32 @test1_neg3(i32 %area) {
+; CHECK-LABEL: @test1_neg3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[AREA:%.*]], 12
+; CHECK-NEXT:    [[REM:%.*]] = and i32 [[MUL]], 4
+; CHECK-NEXT:    ret i32 [[REM]]
+;
+entry:
+  %mul = mul i32 %area, 12
+  %rem = and i32 %mul, 4
+  ret i32 %rem
+}
+
+; Test that the optimization described in PR#51551 is performed
+define i1 @test2(i32 %x, i32 %y) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[X:%.*]], 3
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP0]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  %0 = and i32 %y, -7
+  %1 = or i32 %0, 1
+  %mul = mul nsw i32 %1, %x
+  %and = and i32 %mul, 3
+  %cmp = icmp eq i32 %and, 0
+  ret i1 %cmp
+}
+
+define i1 @test2_2(i32 %x, i32 %y) {
+; CHECK-LABEL: @test2_2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[X:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP0]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  %0 = and i32 %y, -7
+  %1 = or i32 %0, 1
+  %mul = mul nsw i32 %1, %x
+  %and = and i32 %mul, 1
+  %cmp = icmp eq i32 %and, 0
+  ret i1 %cmp
+}
+
+define i1 @test2_neg1(i32 %x, i32 %y) {
+; CHECK-LABEL: @test2_neg1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[Y:%.*]], -4
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[TMP0]], 1
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[MUL]], 7
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  %0 = and i32 %y, -3
+  %1 = or i32 %0, 1
+  %mul = mul nsw i32 %1, %x
+  %and = and i32 %mul, 7
+  %cmp = icmp eq i32 %and, 0
+  ret i1 %cmp
+}
+
+define i1 @test2_neg2(i32 %x, i32 %y) {
+; CHECK-LABEL: @test2_neg2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[Y:%.*]], -7
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[TMP0]], [[X:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[MUL]], 7
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+entry:
+  %0 = and i32 %y, -7
+  %mul = mul nsw i32 %0, %x
+  %and = and i32 %mul, 7
+  %cmp = icmp eq i32 %and, 0
+  ret i1 %cmp
+}
+
+define i32 @test2_neg3(i32 %x, i32 %y) {
+; CHECK-LABEL: @test2_neg3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[Y:%.*]], -8
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[TMP0]], 1
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[MUL]], 7
+; CHECK-NEXT:    ret i32 [[AND]]
+;
+entry:
+  %0 = and i32 %y, -7
+  %1 = or i32 %0, 1
+  %mul = mul nsw i32 %1, %x
+  %and = and i32 %mul, 7
+  ret i32 %and
+}