[InstCombine] Transform (icmp eq/ne rotate(X,AX),rotate(Y,AY)) -> (icmp eq/ne rotate(Y,AX-AY))

[goldstein.w.n]

Summary

Only do so if we don't create more instructions, so either both
rotates have one use or one of the rotates has one use and both AX
and AY are constant.
Proof: https://alive2.llvm.org/ce/z/rVmJgz

[nikic]

It looks like you mixed up the descriptions of the two patches maybe?

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3493

Use CreateIntrinsicCall instead of fetching the declaration manually?

3495

Broken indents

[goldstein.w.n]

In D152348#4402500, @nikic wrote:

It looks like you mixed up the descriptions of the two patches maybe?

Indeed. Fixed.

[goldstein.w.n]

Use Builder.CreateIntrinsic

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3480

Doesn't this also work if the rotates are on different values? https://alive2.llvm.org/ce/z/rVmJgz

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3480

Good catch.

[goldstein.w.n]

support roatate(X) with rotate(Y)

[nikic]

LGTM

[goldstein.w.n]

Rebase

[goldstein.w.n]

Update test

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpEqIntrinsicWithConstant(
   default:
     break;
   }
 
   return nullptr;
 }
 
 /// Fold an icmp with LLVM intrinsics
-static Instruction *foldICmpIntrinsicWithIntrinsic(ICmpInst &Cmp) {
+static Instruction *
+foldICmpIntrinsicWithIntrinsic(ICmpInst &Cmp,
+                               InstCombiner::BuilderTy &Builder) {
   assert(Cmp.isEquality());
 
   ICmpInst::Predicate Pred = Cmp.getPredicate();
   Value *Op0 = Cmp.getOperand(0);
   Value *Op1 = Cmp.getOperand(1);
   const auto *IIOp0 = dyn_cast<IntrinsicInst>(Op0);
   const auto *IIOp1 = dyn_cast<IntrinsicInst>(Op1);
   if (!IIOp0 || !IIOp1 || IIOp0->getIntrinsicID() != IIOp1->getIntrinsicID())
     return nullptr;
 
   switch (IIOp0->getIntrinsicID()) {
   case Intrinsic::bswap:
   case Intrinsic::bitreverse:
     // If both operands are byte-swapped or bit-reversed, just compare the
     // original values.
     return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
   case Intrinsic::fshl:
-  case Intrinsic::fshr:
+  case Intrinsic::fshr: {
     // If both operands are rotated by same amount, just compare the
     // original values.
     if (IIOp0->getOperand(0) != IIOp0->getOperand(1))
       break;
     if (IIOp1->getOperand(0) != IIOp1->getOperand(1))
       break;
-    if (IIOp0->getOperand(2) != IIOp1->getOperand(2))
-      break;
+    if (IIOp0->getOperand(2) == IIOp1->getOperand(2))
       return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
+
+    // rotate(X, AmtX) == rotate(Y, AmtY)
+    //  -> rotate(X, AmtX - AmtY) == Y
+    // Do this if either both rotates have one use or if only one has one use
+    // and AmtX/AmtY are constants.
+    unsigned OneUses = IIOp0->hasOneUse() + IIOp1->hasOneUse();
+    if (OneUses == 2 ||
+        (OneUses == 1 && match(IIOp0->getOperand(2), m_ImmConstant()) &&
+         match(IIOp1->getOperand(2), m_ImmConstant()))) {
+      Value *SubAmt =
+          Builder.CreateSub(IIOp0->getOperand(2), IIOp1->getOperand(2));
+      Value *CombinedRotate = Builder.CreateIntrinsic(
+          Op0->getType(), IIOp0->getIntrinsicID(),
+          {IIOp0->getOperand(0), IIOp0->getOperand(0), SubAmt});
+      return new ICmpInst(Pred, IIOp1->getOperand(0), CombinedRotate);
+    }
+  } break;
   default:
     break;
   }
 
   return nullptr;
 }
 
 /// Try to fold integer comparisons with a constant operand: icmp Pred X, C
 /// where X is some kind of instruction and C is AllowUndef.
 /// TODO: Move more folds which allow undef to this function.
 Instruction *
 InstCombinerImpl::foldICmpInstWithConstantAllowUndef(ICmpInst &Cmp,
if (ShAmt < ASize) {
       APInt CmpV = Cst1->getValue().zext(ASize);
       CmpV <<= ShAmt;
 
       Value *Mask = Builder.CreateAnd(A, Builder.getInt(MaskV));
       return new ICmpInst(Pred, Mask, Builder.getInt(CmpV));
     }
   }
 
-  if (Instruction *ICmp = foldICmpIntrinsicWithIntrinsic(I))
+  if (Instruction *ICmp = foldICmpIntrinsicWithIntrinsic(I, Builder))
     return ICmp;
 
   // Canonicalize checking for a power-of-2-or-zero value:
   // (A & (A-1)) == 0 --> ctpop(A) < 2 (two commuted variants)
   // ((A-1) & A) != 0 --> ctpop(A) > 1 (two commuted variants)
   if (!match(Op0, m_OneUse(m_c_And(m_Add(m_Value(A), m_AllOnes()),
                                    m_Deferred(A)))) ||
       !match(Op1, m_ZeroInt()))

llvm/test/Transforms/InstCombine/icmp-equality-rotate.ll

;
   %x_rorr = call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 %C)
   call void @use.i8(i8 %x_rorr)
   %r = icmp eq i8 %x_rorr, %x
   ret i1 %r
 }
 
 define i1 @cmpne_rorr_rorr(i8 %x, i8 %C0, i8 %C1) {
 ; CHECK-LABEL: @cmpne_rorr_rorr(
-; CHECK-NEXT:    [[X_RORR0:%.*]] = call i8 @llvm.fshr.i8(i8 [[X:%.*]], i8 [[X]], i8 [[C0:%.*]])
-; CHECK-NEXT:    [[X_RORR1:%.*]] = call i8 @llvm.fshr.i8(i8 [[X]], i8 [[X]], i8 [[C1:%.*]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X_RORR0]], [[X_RORR1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i8 [[C0:%.*]], [[C1:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.fshr.i8(i8 [[X:%.*]], i8 [[X]], i8 [[TMP1]])
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[TMP2]], [[X]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x_rorr0 = call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 %C0)
   %x_rorr1 = call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 %C1)
   %r = icmp ne i8 %x_rorr0, %x_rorr1
   ret i1 %r
 }
 
 define i1 @cmpne_rorrX_rorrY(i8 %x, i8 %y, i8 %C0, i8 %C1) {
 ; CHECK-LABEL: @cmpne_rorrX_rorrY(
-; CHECK-NEXT:    [[X_RORR0:%.*]] = call i8 @llvm.fshr.i8(i8 [[X:%.*]], i8 [[X]], i8 [[C0:%.*]])
-; CHECK-NEXT:    [[Y_RORR1:%.*]] = call i8 @llvm.fshr.i8(i8 [[Y:%.*]], i8 [[Y]], i8 [[C1:%.*]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X_RORR0]], [[Y_RORR1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i8 [[C0:%.*]], [[C1:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.fshr.i8(i8 [[X:%.*]], i8 [[X]], i8 [[TMP1]])
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[TMP2]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x_rorr0 = call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 %C0)
   %y_rorr1 = call i8 @llvm.fshr.i8(i8 %y, i8 %y, i8 %C1)
   %r = icmp ne i8 %x_rorr0, %y_rorr1
   ret i1 %r
 }
 
;
   %x_rorl1 = call i8 @llvm.fshl.i8(i8 %x, i8 %x, i8 3)
   call void @use.i8(i8 %x_rorl1)
   %r = icmp ne i8 %x_rorl0, %x_rorl1
   ret i1 %r
 }
 
 define i1 @cmpeq_rorlXC_rorlYC_multiuse1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @cmpeq_rorlXC_rorlYC_multiuse1(
-; CHECK-NEXT:    [[X_RORL0:%.*]] = call i8 @llvm.fshl.i8(i8 [[X:%.*]], i8 [[X]], i8 6)
 ; CHECK-NEXT:    [[Y_RORL1:%.*]] = call i8 @llvm.fshl.i8(i8 [[Y:%.*]], i8 [[Y]], i8 3)
 ; CHECK-NEXT:    call void @use.i8(i8 [[Y_RORL1]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X_RORL0]], [[Y_RORL1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.fshl.i8(i8 [[X:%.*]], i8 [[X]], i8 3)
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[TMP1]], [[Y]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x_rorl0 = call i8 @llvm.fshl.i8(i8 %x, i8 %x, i8 6)
   %y_rorl1 = call i8 @llvm.fshl.i8(i8 %y, i8 %y, i8 3)
   call void @use.i8(i8 %y_rorl1)
   %r = icmp eq i8 %x_rorl0, %y_rorl1
   ret i1 %r
 }

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

;
   %f2 = tail call i8 @llvm.fshl.i8(i8 %y, i8 %y, i8 %z)
   %r = icmp ult i8 %f, %f2
   ret i1 %r
 }
 
 ; negative test - rotate amounts mismatch
 define i1 @amounts_mismatch(i8 %x, i8 %y, i8 %z, i8 %w) {
 ; CHECK-LABEL: @amounts_mismatch(
-; CHECK-NEXT:    [[F:%.*]] = tail call i8 @llvm.fshl.i8(i8 [[X:%.*]], i8 [[X]], i8 [[Z:%.*]])
-; CHECK-NEXT:    [[F2:%.*]] = tail call i8 @llvm.fshl.i8(i8 [[Y:%.*]], i8 [[Y]], i8 [[W:%.*]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[F]], [[F2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i8 [[Z:%.*]], [[W:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.fshl.i8(i8 [[X:%.*]], i8 [[X]], i8 [[TMP1]])
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[TMP2]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %f = tail call i8 @llvm.fshl.i8(i8 %x, i8 %x, i8 %z)
   %f2 = tail call i8 @llvm.fshl.i8(i8 %y, i8 %y, i8 %w)
   %r = icmp eq i8 %f, %f2
   ret i1 %r
 }