[InstCombine] rotate(X,Z) eq/ne rotate(Y,Z) ---> X eq/ne Y (PR51565)

[xbolva00]

Summary

----------------------------------------
define i1 @src(i8 %x, i8 %y, i8 %z) {
%0:
  %f = fshl i8 %x, i8 %x, i8 %z
  %f2 = fshl i8 %y, i8 %y, i8 %z
  %r = icmp eq i8 %f, %f2
  ret i1 %r
}
=>
define i1 @tgt(i8 %x, i8 %y, i8 %z) {
%0:
  %r = icmp eq i8 %x, %y
  ret i1 %r
}
Transformation seems to be correct!

https://alive2.llvm.org/ce/z/qAZp8f

Solves PR51565

[spatel]

LGTM - see inline for a nit (so might be worth adding the new function as an NFC pre-commit).

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3266

This can be an assert, right? We're called only by foldICmpEquality(), so it already checked.

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3266

Yeah, I was thinking about it too.

[xbolva00]

Addressed review comments.

[xbolva00]

In D109271#2983670, @spatel wrote:

LGTM - see inline for a nit (so might be worth adding the new function as an NFC pre-commit).

Sure! Thanks.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpEqIntrinsicWithConstant(
   }
   default:
     break;
   }
 
   return nullptr;
 }
 
+/// Fold an icmp with LLVM intrinsics
+static Instruction *foldICmpIntrinsicWithIntrinsic(ICmpInst &Cmp) {
+  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:
+    // 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;
+    return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
+  default:
+    break;
+  }
+
+  return nullptr;
+}
+
 /// Fold an icmp with LLVM intrinsic and constant operand: icmp Pred II, C.
 Instruction *InstCombinerImpl::foldICmpIntrinsicWithConstant(ICmpInst &Cmp,
                                                              IntrinsicInst *II,
                                                              const APInt &C) {
   if (Cmp.isEquality())
     return foldICmpEqIntrinsicWithConstant(Cmp, II, C);
 
   Type *Ty = II->getType();
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 both operands are byte-swapped or bit-reversed, just compare the
-  // original values.
-  // TODO: Move this to a function similar to foldICmpIntrinsicWithConstant()
-  // and handle more intrinsics.
-  if ((match(Op0, m_BSwap(m_Value(A))) && match(Op1, m_BSwap(m_Value(B)))) ||
-      (match(Op0, m_BitReverse(m_Value(A))) &&
-       match(Op1, m_BitReverse(m_Value(B)))))
-    return new ICmpInst(Pred, A, B);
+  if (Instruction *ICmp = foldICmpIntrinsicWithIntrinsic(I))
+    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()))
     A = nullptr;

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 declare i8 @llvm.fshl.i8(i8, i8, i8)
 declare i8 @llvm.fshr.i8(i8, i8, i8)
 declare <2 x i5> @llvm.fshl.v2i5(<2 x i5>, <2 x i5>, <2 x i5>)
 declare <2 x i5> @llvm.fshr.v2i5(<2 x i5>, <2 x i5>, <2 x i5>)
 declare void @use(i8)
 
 define i1 @rol_eq(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @rol_eq(
-; 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 [[Z]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[F]], [[F2]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X:%.*]], [[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 %z)
   %r = icmp eq i8 %f, %f2
   ret i1 %r
 }
 
 define i1 @rol_ne(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @rol_ne(
-; 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 [[Z]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[F]], [[F2]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X:%.*]], [[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 %z)
   %r = icmp ne i8 %f, %f2
   ret i1 %r
 }
 
 define i1 @ror_eq(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @ror_eq(
-; CHECK-NEXT:    [[F:%.*]] = tail call i8 @llvm.fshr.i8(i8 [[X:%.*]], i8 [[X]], i8 [[Z:%.*]])
-; CHECK-NEXT:    [[F2:%.*]] = tail call i8 @llvm.fshr.i8(i8 [[Y:%.*]], i8 [[Y]], i8 [[Z]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[F]], [[F2]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %f = tail call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 %z)
   %f2 = tail call i8 @llvm.fshr.i8(i8 %y, i8 %y, i8 %z)
   %r = icmp eq i8 %f, %f2
   ret i1 %r
 }
 
 
 define i1 @ror_ne(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @ror_ne(
-; CHECK-NEXT:    [[F:%.*]] = tail call i8 @llvm.fshr.i8(i8 [[X:%.*]], i8 [[X]], i8 [[Z:%.*]])
-; CHECK-NEXT:    [[F2:%.*]] = tail call i8 @llvm.fshr.i8(i8 [[Y:%.*]], i8 [[Y]], i8 [[Z]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[F]], [[F2]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %f = tail call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 %z)
   %f2 = tail call i8 @llvm.fshr.i8(i8 %y, i8 %y, i8 %z)
   %r = icmp ne i8 %f, %f2
   ret i1 %r
 }
 
 define i1 @rol_eq_use(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @rol_eq_use(
 ; CHECK-NEXT:    [[F:%.*]] = tail call i8 @llvm.fshl.i8(i8 [[X:%.*]], i8 [[X]], i8 [[Z:%.*]])
 ; CHECK-NEXT:    call void @use(i8 [[F]])
-; CHECK-NEXT:    [[F2:%.*]] = tail call i8 @llvm.fshl.i8(i8 [[Y:%.*]], i8 [[Y]], i8 [[Z]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[F]], [[F2]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %f = tail call i8 @llvm.fshl.i8(i8 %x, i8 %x, i8 %z)
   call void @use(i8 %f)
   %f2 = tail call i8 @llvm.fshl.i8(i8 %y, i8 %y, i8 %z)
   %r = icmp eq i8 %f, %f2
   ret i1 %r
 }
 
 define i1 @rol_eq_uses(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @rol_eq_uses(
 ; CHECK-NEXT:    [[F:%.*]] = tail call i8 @llvm.fshl.i8(i8 [[X:%.*]], i8 [[X]], i8 [[Z:%.*]])
 ; CHECK-NEXT:    call void @use(i8 [[F]])
 ; CHECK-NEXT:    [[F2:%.*]] = tail call i8 @llvm.fshl.i8(i8 [[Y:%.*]], i8 [[Y]], i8 [[Z]])
 ; CHECK-NEXT:    call void @use(i8 [[F2]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[F]], [[F2]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %f = tail call i8 @llvm.fshl.i8(i8 %x, i8 %x, i8 %z)
   call void @use(i8 %f)
   %f2 = tail call i8 @llvm.fshl.i8(i8 %y, i8 %y, i8 %z)
   call void @use(i8 %f2)
   %r = icmp eq i8 %f, %f2
   ret i1 %r
 }
 
 define <2 x i1> @rol_eq_vec(<2 x i5> %x, <2 x i5> %y, <2 x i5> %z) {
 ; CHECK-LABEL: @rol_eq_vec(
-; CHECK-NEXT:    [[F:%.*]] = tail call <2 x i5> @llvm.fshl.v2i5(<2 x i5> [[X:%.*]], <2 x i5> [[X]], <2 x i5> [[Z:%.*]])
-; CHECK-NEXT:    [[F2:%.*]] = tail call <2 x i5> @llvm.fshl.v2i5(<2 x i5> [[Y:%.*]], <2 x i5> [[Y]], <2 x i5> [[Z]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i5> [[F]], [[F2]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i5> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %f = tail call <2 x i5> @llvm.fshl.v2i5(<2 x i5> %x, <2 x i5> %x, <2 x i5> %z)
   %f2 = tail call <2 x i5> @llvm.fshl.v2i5(<2 x i5> %y, <2 x i5> %y, <2 x i5> %z)
   %r = icmp eq <2 x i5> %f, %f2
   ret <2 x i1> %r
 }
 
 define <2 x i1> @ror_eq_vec(<2 x i5> %x, <2 x i5> %y, <2 x i5> %z) {
 ; CHECK-LABEL: @ror_eq_vec(
-; CHECK-NEXT:    [[F:%.*]] = tail call <2 x i5> @llvm.fshr.v2i5(<2 x i5> [[X:%.*]], <2 x i5> [[X]], <2 x i5> [[Z:%.*]])
-; CHECK-NEXT:    [[F2:%.*]] = tail call <2 x i5> @llvm.fshr.v2i5(<2 x i5> [[Y:%.*]], <2 x i5> [[Y]], <2 x i5> [[Z]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i5> [[F]], [[F2]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i5> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %f = tail call <2 x i5> @llvm.fshr.v2i5(<2 x i5> %x, <2 x i5> %x, <2 x i5> %z)
   %f2 = tail call <2 x i5> @llvm.fshr.v2i5(<2 x i5> %y, <2 x i5> %y, <2 x i5> %z)
   %r = icmp eq <2 x i5> %f, %f2
   ret <2 x i1> %r
 }