[InstCombine] Canonicalize (icmp eq/ne X, rotate(X)) to always use rotate-left

[goldstein.w.n]

Summary

We canonicalize rotate-right -> rotate-left in other places. Makes
sense to do so here as well.
Proof: https://alive2.llvm.org/ce/z/HL3TpK

[goldstein.w.n]

Use Builder.CreateIntrinsic

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5053

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (match(Op0, m_c_And(m_Specific(Op1), m_Value())) &&
     return new ICmpInst(CmpInst::getInversePredicate(Pred), Op0,
                         ConstantInt::getNullValue(Op0->getType()));
 
   if (match(Op1, m_c_And(m_Specific(Op0), m_Value())) &&
       isKnownToBeAPowerOfTwo(Op0, /* OrZero */ false, 0, &I))
     return new ICmpInst(CmpInst::getInversePredicate(Pred), Op1,
                         ConstantInt::getNullValue(Op1->getType()));
 
+  // Canonicalize:
+  // icmp eq/ne X, OneUse(rotate-right(X))
+  //    -> icmp eq/ne X, rotate-left(X)
+  // We generally try to convert rotate-right -> rotate-left, this just
+  // canonicalizes another case.
+  CmpInst::Predicate PredUnused = Pred;
+  if (match(&I, m_c_ICmp(PredUnused, m_Value(A),
+                         m_OneUse(m_Intrinsic<Intrinsic::fshr>(
+                             m_Deferred(A), m_Deferred(A), m_Value(B))))))
+    return new ICmpInst(
+        Pred, A,
+        Builder.CreateIntrinsic(Op0->getType(), Intrinsic::fshl, {A, A, B}));
+
   return nullptr;
 }
 
 Instruction *InstCombinerImpl::foldICmpWithTrunc(ICmpInst &ICmp) {
   ICmpInst::Predicate Pred = ICmp.getPredicate();
   Value *Op0 = ICmp.getOperand(0), *Op1 = ICmp.getOperand(1);
 
   // Try to canonicalize trunc + compare-to-constant into a mask + cmp.

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare i8 @llvm.fshl.i8(i8, i8, i8)
 declare i8 @llvm.fshr.i8(i8, i8, i8)
 declare void @use.i8(i8)
 define i1 @cmpeq_rorr_to_rorl(i8 %x, i8 %C) {
 ; CHECK-LABEL: @cmpeq_rorr_to_rorl(
-; CHECK-NEXT:    [[X_RORR:%.*]] = call i8 @llvm.fshr.i8(i8 [[X:%.*]], i8 [[X]], i8 [[C:%.*]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X_RORR]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.fshl.i8(i8 [[X:%.*]], i8 [[X]], i8 [[C:%.*]])
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[TMP1]], [[X]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x_rorr = call i8 @llvm.fshr.i8(i8 %x, i8 %x, i8 %C)
   %r = icmp eq i8 %x_rorr, %x
   ret i1 %r
 }
 
 define i1 @cmpeq_rorr_to_rorl_non_equality_fail(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:    [[TMP1:%.*]] = sub i8 [[C0:%.*]], [[C1:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.fshr.i8(i8 [[X:%.*]], i8 [[X]], i8 [[TMP1]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.fshl.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
 }