[InstCombine] ror/rol(X, RotAmt) == C --> X == rol/ror(C, RotAmt) (PR51567)

[xbolva00]

Summary

----------------------------------------
define i1 @src(i32 %0) {
%1:
  %2 = fshl i32 %0, i32 %0, i32 25
  %3 = icmp eq i32 %2, 5
  ret i1 %3
}
=>
define i1 @tgt(i32 %0) {
%1:
  %2 = icmp eq i32 %0, 640
  ret i1 %2
}
Transformation seems to be correct!

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

Solves PR51567

[xbolva00]

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

150

Enough tests?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3238

Calling this "RotC" or "RotAmtC" makes it more obvious that we are matching a constant.

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

115

The over-shifting isn't relevant - please reduce to a valid amount (for example 28 -> 4) in this test and others.
But don't use "4" with a bitwidth of 8 either because that makes the test ambiguous about whether it is rotating in the wrong direction.

150

We're missing a fshl with ne. Also at least one extra-use test should be here.
Please pre-commit baseline tests.

[xbolva00]

Addressed review comments

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

                           IsZero ? Constant::getNullValue(Ty)
                                  : Constant::getAllOnesValue(Ty));
 
     break;
   }
 
   case Intrinsic::fshl:
   case Intrinsic::fshr:
-    // (rot X, ?) == 0/-1 --> X == 0/-1
-    // TODO: This transform is safe to re-use undef elts in a vector, but
-    //       the constant value passed in by the caller doesn't allow that.
-    if (C.isNullValue() || C.isAllOnesValue())
-      if (II->getArgOperand(0) == II->getArgOperand(1))
+    if (II->getArgOperand(0) == II->getArgOperand(1)) {
+      // (rot X, ?) == 0/-1 --> X == 0/-1
+      // TODO: This transform is safe to re-use undef elts in a vector, but
+      //       the constant value passed in by the caller doesn't allow that.
+      if (C.isNullValue() || C.isAllOnesValue())
         return new ICmpInst(Pred, II->getArgOperand(0), Cmp.getOperand(1));
+
+      const APInt *RotAmt;
+      // ror(X, RotAmt) == C --> X == rol(C, RotAmt)
+      // rol(X, RotAmt) == C --> X == ror(C, RotAmt)
+      if (match(II->getArgOperand(2), m_APInt(RotAmt)))
+        return new ICmpInst(Pred, II->getArgOperand(0),
+                            II->getIntrinsicID() == Intrinsic::fshl
+                                ? ConstantInt::get(Ty, C.rotr(*RotAmt))
+                                : ConstantInt::get(Ty, C.rotl(*RotAmt)));
+    }
     break;
 
   case Intrinsic::uadd_sat: {
     // uadd.sat(a, b) == 0  ->  (a | b) == 0
     if (C.isNullValue()) {
       Value *Or = Builder.CreateOr(II->getArgOperand(0), II->getArgOperand(1));
       return new ICmpInst(Pred, Or, Constant::getNullValue(Ty));
     }

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 <32 x i32> @llvm.fshl.v32i32(<32 x i32>, <32 x i32>, <32 x i32>)
 declare void @use(i8)
 
 define i1 @rol_eq(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @rol_eq(
 ; 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)

 ; 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
 }
 
+
+define i1 @rol_eq_cst(i8 %x) {
+; CHECK-LABEL: @rol_eq_cst(
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X:%.*]], 32
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %f = tail call i8 @llvm.fshl.i8(i8 %x, i8 %x, i8 28)
+  %r = icmp eq i8 %f, 2
+  ret i1 %r
+}
+
+define i1 @ror_eq_cst(i8 %x) {
+; CHECK-LABEL: @ror_eq_cst(
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X:%.*]], 16
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %f = tail call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 27)
+  %r = icmp eq i8 %f, 2
+  ret i1 %r
+}
+
+define i1 @ror_ne_cst(i8 %x) {
+; CHECK-LABEL: @ror_ne_cst(
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X:%.*]], 24
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %f = tail call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 27)
+  %r = icmp ne i8 %f, 3
+  ret i1 %r
+}
+
+define <2 x i1> @rol_eq_cst_vec(<2 x i5> %x) {
+; CHECK-LABEL: @rol_eq_cst_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i5> [[X:%.*]], <i5 -16, i5 -16>
+; 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> <i5 3, i5 3>)
+  %r = icmp eq <2 x i5> %f, <i5 2, i5 2>
+  ret <2 x i1> %r
+}
+
+define <2 x i1> @rol_eq_cst_undef(<2 x i5> %x) {
+; CHECK-LABEL: @rol_eq_cst_undef(
+; CHECK-NEXT:    [[F:%.*]] = call <2 x i5> @llvm.fshl.v2i5(<2 x i5> [[X:%.*]], <2 x i5> [[X]], <2 x i5> <i5 2, i5 2>)
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i5> [[F]], <i5 2, i5 undef>
+; 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> <i5 3, i5 3>)
+  %r = icmp eq <2 x i5> %f, <i5 2, i5 undef>
+  ret <2 x i1> %r
+}
+
 ; negative test - not a rotate
 define i1 @no_rotate(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @no_rotate(
 ; CHECK-NEXT:    [[F:%.*]] = tail call i8 @llvm.fshl.i8(i8 [[X:%.*]], i8 [[Y:%.*]], 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:    ret i1 [[R]]
 ;

 ; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[F]], [[F2]]
 ; 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
 }
+
+; negative test - wrong predicate
+define i1 @wrong_pred2(i8 %x) {
+; CHECK-LABEL: @wrong_pred2(
+; CHECK-NEXT:    [[F:%.*]] = call i8 @llvm.fshl.i8(i8 [[X:%.*]], i8 [[X]], i8 5)
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[F]], 2
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %f = tail call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 27)
+  %r = icmp ugt i8 %f, 2
+  ret i1 %r
+}